Pagini recente » Cod sursa (job #364470) | Cod sursa (job #2066415) | Cod sursa (job #1201293) | Cod sursa (job #3134636) | Cod sursa (job #669739)
Cod sursa(job #669739)
#include <cstdio>
#include <cstdlib>
struct point
{
double x,y;
};
point *a;
int compar_upolar(const void *p1,const void *p2)
{
if(((*(struct point *)p1).x-a[0].x)*((*(struct point *)p2).y-a[0].y)<((*(struct point *)p1).y-a[0].y)*((*(struct point *)p2).x-a[0].x))
return 1;
return 0;
}
inline int isleft(double ax,double ay,double bx,double by)
{
return ax*by>ay*bx;
}
void citire(int &n)
{
FILE *f=fopen("infasuratoare.in","r");
fscanf(f,"%d\n",&n);
int i=n-1,pinit=0;
a=(point*)malloc(sizeof(point)*(n));
fscanf(f,"%lf %lf\n",&a[0].x,&a[0].y);
while(i)
{
fscanf(f,"%lf %lf\n",&a[i].x,&a[i].y);
if(a[i].x<a[pinit].x||(a[i].x==a[pinit].x&&a[i].y<a[pinit].y))
pinit=i;
i--;
}
point tmp=a[pinit];
a[pinit]=a[0];
a[0]=tmp;
}
void afisare(point* st,int n)
{
int i;
FILE* f=fopen("infasuratoare.out","w");
fprintf(f,"%d\n",n+1);
for(i=0;i<=n;i++)
fprintf(f,"%lf %lf\n",st[i].x,st[i].y);
}
point* conv_hull(int n,int &h)
{
point *st=(point*)malloc(n*sizeof(point));
int i;
qsort(a+1,n-1,sizeof(point),compar_upolar);
st[0]=a[0];
st[1]=a[1];
h=1;
for(i=2;i<n;++i)
{
while(!isleft(st[h].x-st[h-1].x,st[h].y-st[h-1].y,a[i].x-st[h].x,a[i].y-st[h].y)) h--;
++h;
st[h]=a[i];
}
return st;
}
int main()
{
int n,h;
point *st;
citire(n);
st=conv_hull(n,h);
afisare(st,h);
return 0;
}