Pagini recente » Cod sursa (job #790996) | Cod sursa (job #419361) | Cod sursa (job #1926932) | Cod sursa (job #505297) | Cod sursa (job #2416801)
#include <bits/stdc++.h>
#define maxN 120002
#define ty double
#define eps 1e-12
using namespace std;
FILE *fin = freopen("infasuratoare.in", "r", stdin);
FILE *fout = freopen("infasuratoare.out", "w", stdout);
struct Point
{
ty x, y;
bool operator < (const Point &ot) const
{
if (fabs(x - ot.x) < eps) return y < ot.y;
return x < ot.x;
}
ty CrossProd(const Point &O, const Point &B)
{
return (x - O.x) * (B.y - O.y) - (B.x - O.x) * (y - O.y);
}
} v[maxN];
int n;
int head, st[maxN];
bool vis[maxN];
void ConvHull()
{
sort(v, v + n);
head = 2;
vis[1] = true;
st[0] = 0;
st[1] = 1;
int sgn = 1;
for (int i = 0; i >= 0; i += sgn)
{
if (vis[i]) continue;
while (head > 1 && v[st[head - 2]].CrossProd(v[st[head - 1]], v[i]) < eps)
vis[st[-- head]] = false;
st[head ++] = i;
vis[i] = true;
if (i == n - 1)
sgn = -sgn;
}
-- head;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++ i)
scanf("%lf %lf", &v[i].x, &v[i].y);
ConvHull();
printf("%d\n", head);
for (int i = 0; i < head; ++ i)
printf("%.12lf %.12lf\n", v[st[i]].x, v[st[i]].y);
return 0;
}