Pagini recente » Cod sursa (job #584032) | Cod sursa (job #1864037) | Cod sursa (job #2538858) | Cod sursa (job #1896692) | Cod sursa (job #268515)
Cod sursa(job #268515)
#include<stdio.h>
#include<stdlib.h>
#define nmax 120010
FILE *f=fopen("infasuratoare.in","r"), *g=fopen("infasuratoare.out","w");
struct punct { double x,y;} a[nmax],pst;
int n,i;
inline int isleft(punct p1, punct p2, punct p3)
{
return ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y));
}
inline int cmp(punct *p1, punct *p2)
{
int left=isleft(pst,*p1,*p2);
if(left>0) return -1;
if(left==0) return 0;
if(left<0) return 1;
}
int main()
{
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
fscanf(f,"%lf %lf",&a[i].x, &a[i].y);
pst=a[1];
int poz=1;
for(i=2;i<=n;i++)
if(a[i].y<pst.y) pst=a[i],poz=i;
else
if(a[i].y==pst.y)
if(a[i].x<pst.x) pst=a[i],poz=i;
punct aux;
aux=a[1];
a[1]=a[poz];
a[poz]=aux;
qsort(a+2,n-1,sizeof(punct), (int (*)(const void *, const void *))cmp);
punct stiva[nmax];
stiva[1]=a[1];
stiva[2]=a[2];
stiva[3]=a[3];
int k=3;
for(i=4;i<=n;i++)
{
while(isleft(stiva[k-1],stiva[k],a[i])<0) k--;
stiva[++k]=a[i];
}
fprintf(g,"%d\n",k);
for(i=1;i<=k;i++) fprintf(g,"%.6lf %.6lf\n",stiva[i].x,stiva[i].y);
fclose(f);
fclose(g);
return 0;
}