Pagini recente » Cod sursa (job #742416) | Cod sursa (job #1350272) | Cod sursa (job #1819541) | Cod sursa (job #154970) | Cod sursa (job #2376103)
#include <bits/stdc++.h>
#define MAXN 121000
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{ double x;
double y;
}v[MAXN];
double det(punct a, punct b, punct c)
{ double d=(a.x*b.y)+(b.x*c.y)+(c.x*a.y)-(c.x*b.y)-(b.x*a.y)-(a.x*c.y);
return d;
}
bool cmp(punct a, punct b)
{ double D=det(v[1],a,b);
return D>0;
}
int a[MAXN],n,k;
int main()
{ f>>n;
for(int i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
for(int i=2;i<=n;i++)
if(v[1].x>v[i].x || (v[1].x==v[i].x && v[1].y>v[i].y)) swap(v[1],v[i]);
sort(v+2,v+n+1,cmp);
a[++k]=1;
a[++k]=2;
for(int i=3;i<=n;i++)
{ while(k>=2 && det(v[a[k-1]],v[a[k]],v[i])<0) k--;
a[++k]=i;
}
g<<k<<'\n';
for(int i=1;i<=k;i++)
g<<setprecision(12)<<fixed<<v[a[i]].x<<" "<<v[a[i]].y<<'\n';
return 0;
}