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