Pagini recente » Cod sursa (job #1525325) | Cod sursa (job #2571602) | Cod sursa (job #350123) | Cod sursa (job #2981908) | Cod sursa (job #1841210)
#include <bits/stdc++.h>
#define Point pair <double, double>
#define x first
#define y second
FILE *fin = freopen("infasuratoare.in", "r", stdin);
FILE *fout = freopen("infasuratoare.out", "w", stdout);
using namespace std;
const int NMAX = 120005;
const double ZERO = 1e-12;
int N;
Point v[NMAX];
bitset <NMAX> vis;
int st[NMAX], head;
void read()
{
scanf("%d", &N);
for (int i = 1; i <= N; ++ i)
scanf("%lf %lf\n", &v[i].x, &v[i].y);
}
double cross_product(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;
vis.set(2);
for (int i = 1, p = 1; i > 0; i += (p = (i == N ? -p : p)))
{
if (vis.test(i)) continue;
while (head > 1 && cross_product(v[st[head - 1]], v[st[head]], v[i]) < ZERO)
vis.reset(st[head --]);
st[++ head] = i;
vis.set(i);
}
}
void write()
{
printf("%d\n", head - 1);
for (int i = 1; i < head; ++ i)
printf("%.6lf %.6lf\n", v[st[i]].first, v[st[i]].second);
}
int main()
{
read();
convex_hull();
write();
}