Pagini recente » Cod sursa (job #952878) | Cod sursa (job #730159) | Cod sursa (job #3271103) | Cod sursa (job #316732) | Cod sursa (job #348956)
Cod sursa(job #348956)
#include<stdio.h>
#include<algorithm>
using namespace std;
int i,n,d,sor[12010],stiva[12010];
struct point
{ long double x,y;
}p[120010],q;
inline long double isleft(point a, point b, point c)
{ return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool comp( int i, int j)
{
long double k=isleft(p[0],p[i],p[j]);
if( k>0) return 1;
else if(k==0&&p[i].y!=p[j].y) return p[i].y<p[j].y;
return 0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
scanf("%LE %LE",&p[0].x,&p[0].y);
q=p[0];
for(i=1;i<n;i++) { scanf("%LE %LE",&p[i].x,&p[i].y);
if(p[i].y<p[0].y||(p[i].y==p[0].y&&p[i].x>p[0].x)) { q=p[i];
p[i]=p[0];
p[0]=q;
}
sor[i]=i;
}
p[n]=p[0];
p[n+1]=p[1];
sort(sor+1,sor+n,comp);
for(i=1;i<n;i++) { while(d>0&&isleft(p[stiva[d-1]],p[stiva[d]],p[sor[i]])<=0) d--;
stiva[++d]=sor[i];
}
printf("%d\n",d+1);
for(i=0;i<=d;i++) printf("%LE %LE\n",p[stiva[i]].x,p[stiva[i]].y);
fclose(stdin);
fclose(stdout);
return 0;
}