Pagini recente » Cod sursa (job #329874) | Cod sursa (job #2076913) | Cod sursa (job #3191691) | Cod sursa (job #29927) | Cod sursa (job #268527)
Cod sursa(job #268527)
#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)
{
int left=((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y));
return left;
}
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];
int k;
stiva[++k]=a[1];
for(i=2;i<=n;i++)
{
while(k>1 && isleft(stiva[k-1],stiva[k],a[i])<0) k--;
stiva[++k]=a[i];
}
while (k > 1 && isleft(stiva[k],stiva[k],a[1])<0) k--;
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;
}