Pagini recente » Cod sursa (job #2716124) | Cod sursa (job #3187528) | Cod sursa (job #1276273) | Cod sursa (job #1023787) | Cod sursa (job #2618097)
#include <bits/stdc++.h>
#define infile "infasuratoare.in"
#define outfile "infasuratoare.out"
#define x first
#define y second
typedef std::pair<double, double> Point;
const int NMAX = 120005;
const double EPS = 1e-12;
int n, st[NMAX], head;
Point v[NMAX];
std::bitset<NMAX> viz;
double crossProduct(Point O, Point A, Point B)
{
return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}
void convex_hull()
{
sort(v + 1, v + n + 1);
st[1] = 1;
st[2] = 2;
head = 2;
viz[2] = 1;
for (int i = 1, p = 1; i > 0; i += (p = (i == n ? -p : p)))
{
if (viz[i]) continue;
while (head >= 2 && crossProduct(v[st[head-1]], v[st[head]], v[i]) < EPS)
viz[st[head--]] = 0;
st[++head] = i;
viz[i] = true;
}
std::cout << head - 1 << "\n";
std::cout << std::setprecision(6) << std::fixed;
for (int i = 1; i < head; ++i)
{
std::cout << v[st[i]].x << " " << v[st[i]].y << "\n";
}
}
int main()
{
freopen(infile, "r", stdin);
freopen(outfile, "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
std::cin >> v[i].x >> v[i].y;
}
convex_hull();
fclose(stdin);
fclose(stdout);
return 0;
}