Pagini recente » Cod sursa (job #2560205) | Cod sursa (job #140507) | Cod sursa (job #25419) | Cod sursa (job #708209) | Cod sursa (job #399217)
Cod sursa(job #399217)
#include<stdio.h>
#include<math.h>
#include<search.h>
#include<stdlib.h>
#define max 120001
int i,j,min,n,px,py,vect[max],st[max];
double vx[max],vy[max],up[max];
int sort_function(const void *x,const void *y)
{ int a,b;
a=*(int *)x;
b=*(int *)y;
if( up[a]- up[b]>0)
return 5454;
else return -58;
}
long double semn(int a,int b, int c)
{
return (long double) ( vx[a]*vy[b]+vx[b]*vy[c]+vx[c]*vy[a]-vy[a]*vx[b]-vy[b]*vx[c]-vy[c]*vx[a]);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d\n",&n);
scanf("%lf %lf",&vx[1],&vy[1]);
min=1;
vect[1]=1;
for(i=2;i<=n;i++)
{
scanf("%lf %lf",&vx[i],&vy[i]);
if(vy[i]<vy[min] || ( vy[i]==vy[min] && vx[i]<vx[min]))
min=i;
vect[i]=i;
}
px=vx[min];
py=vy[min];
for(i=1;i<=n;i++)
{
if(i!=min)
{
double aux=pow(vx[i]-px,2)+pow(vy[i]-py,2);
aux=sqrt(aux);
up[i]=(double)(px-vx[i])/aux;
}}
qsort(vect+1, n, sizeof(vect[1]),sort_function);
st[1]=min;
st[2]=vect[1];
st[3]=vect[2];
j=3;
for(i=3;i<=n;i++)
{
if(vect[i]!=min)
{
while(j>=2 && semn(st[j-1],st[j],vect[i])<0) --j;
st[++j]=vect[i];
}
}
st[0]=min;
printf("%d\n",j);
for(i=1;i<=j;i++)
{
printf("%lf %lf\n",vx[st[i]],vy[st[i]]);
}
return 0;
}