Pagini recente » Cod sursa (job #940672) | Cod sursa (job #1500583)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 120005;
struct point {double x, y;} v[nmax], st[nmax];
double det(point a, point b, point c)
{
return ((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y));
}
inline int cmp(point a, point b)
{
return det(v[1], a, b) < 0;
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int i, n, top=0;
scanf("%d", &n);
for(i=1; i<=n; i++)
scanf("%lf %lf", &v[i].x, &v[i].y);
sort(v+1, v+n+1, cmp);
st[++top]=v[1];
st[++top]=v[2];
for(i=3; i<=n; i++)
{
while(top>=2 && det(st[top-1], st[top], v[i])>0) --top;
st[++top]=v[i];
}
printf("%d\n", top);
while(top>0)
{
printf("%.6lf %.6lf\n", st[top].x, st[top].y);
top--;
}
fclose(stdin);
fclose(stdout);
return 0;
}