Pagini recente » Cod sursa (job #91029) | Cod sursa (job #2569353) | Cod sursa (job #2246925) | Cod sursa (job #412470) | Cod sursa (job #291123)
Cod sursa(job #291123)
#include<stdio.h>
#include<algorithm>
using namespace std;
struct punct {float x,y,tg;}sigur,v[12010],c[12010];
int i,j,k,l,m,n;
int arie(double a,double b,double d,double e,double g,double h)
{return (a*e+b*g+d*h)-(g*e+h*a+d*b);
}
int cmp(punct a,punct b){
return a.tg>b.tg;
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
sigur.x=sigur.y=(float (1))/(float(0));
for(i=1;i<=n;i++)
{scanf("%f %f",&v[i].x,&v[i].y);
if(v[i].x<sigur.x)sigur=v[i];
else
if(v[i].x==sigur.x&&v[i].y<sigur.y)sigur=v[i];
}
k=0;
for(i=1;i<=n;i++)
if(v[i].x!=sigur.x||v[i].y!=sigur.y)
{k++;
v[k]=v[i];
v[k].tg=(v[i].y-sigur.y)/(v[i].x-sigur.x);}
sort(v+1,v+n,cmp);
n=n-1;
c[1]=sigur;
c[2]=v[1];
k=2;
for(i=2;i<=n;i++)
{while(arie(c[k-1].x,c[k-1].y,c[k].x,c[k].y,v[i].x,v[i].y)>0&&k>=2)k--;
k++;
c[k]=v[i];
}
printf("%d\n",k);
for(i=1;i<=k;i++)
printf("%0.4f %0.4f\n",c[i].x,c[i].y);
return 0;}