Pagini recente » Cod sursa (job #3232472) | Cod sursa (job #2174542) | Cod sursa (job #460382) | Cod sursa (job #87061) | Cod sursa (job #2165488)
#include <bits/stdc++.h>
#define MAX 120001
using namespace std;
int n,i,cnt,ap[MAX],q;
int stck[MAX];
struct str
{
double x,y;
}v[MAX];
bool cmp(str a, str b)
{
if(a.x<b.x) return 1;
else
if(a.x==b.x&&a.y<b.y) return 1;
return 0;
}
double det (str a, str b, str c)
{
if(a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-b.x*a.y<0.0) return 1;
return 0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
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);
stck[1]=1;
stck[2]=2;
ap[2]=1;
cnt=2;
q=1;
i=3;
while(!ap[1])
{
while(ap[i])
{
if(i==n)q=-1;
i+=q;
}
while(cnt>=2&&!det(v[stck[cnt]],v[stck[cnt-1]],v[i]))
ap[stck[cnt]]=0,cnt--;
stck[++cnt]=i;
ap[i]=1;
}
printf("%d\n",cnt-1);
for(i=2;i<=cnt;i++)
printf("%lf %lf\n",v[stck[i]].x,v[stck[i]].y);
return 0;
}