Pagini recente » Cod sursa (job #1580165) | Cod sursa (job #179311) | Cod sursa (job #1488746) | Cod sursa (job #346954) | Cod sursa (job #1922430)
#include <cstdio>
#include <algorithm>
using namespace std;
struct punct
{
double x,y;
}v[120010],q[120010];
double det(punct &a,punct &b,punct &c)
{
return (a.x-b.x)*(a.y-c.y)-(a.x-c.x)*(a.y-b.y);
}
int cmp(punct a,punct b)
{
return det(v[1],a,b)>0;
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n,nr=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf%lf",&v[i].x,&v[i].y);
for(int i=2;i<=n;i++)
if(v[i].x<v[1].x) swap(v[1],v[i]);
sort(v+2,v+1+n,cmp);
for(int i=1;i<=n;i++)
{
while(nr>=2 && det(q[nr-1],q[nr],v[i])<0) nr--;
q[++nr]=v[i];
}
printf("%d\n",nr);
for(int i=1;i<=nr;i++)
printf("%.12f %.12f\n",q[i].x,q[i].y);
return 0;
}