Pagini recente » Cod sursa (job #1186247) | Cod sursa (job #381087) | Cod sursa (job #276572) | Cod sursa (job #2010800) | Cod sursa (job #267002)
Cod sursa(job #267002)
#include<fstream.h>
#include<stdio.h>
ifstream fin("infasuratoare.in");
struct punct { double x,y;
} a[120200];
int u=1,s[120200];
long n;
double min=1000000,min1=1000000;
int sgn(punct b,punct c,punct d)
{
long double semn=((b.x-d.x)*(c.y-d.y)-(b.y-d.y)*(c.x-d.x));
if(semn>0) return 1;
if(semn<0) return -1;
return 0;
}
void sort(int x,int y)
{ int i=x,j=y;
punct p=a[(i+j)/2],aux;
do {
while(sgn(a[1],a[i],p)==1) ++i;
while(sgn(a[1],p,a[j])==1) --j;
if(i<=j) { aux=a[i];
a[i]=a[j];
a[j]=aux;
++i;
--j;
}
} while(i<=j);
if(x<j) sort(x,j);
if(i<y) sort(i,y);
}
int main()
{ int i;
freopen("infasuratoare.out","w",stdout);
fin>>n;
for(i=1;i<=n;i++)
{ fin>>a[i].x>>a[i].y;
if(a[i].y<min){ min=a[i].y;
min1=a[i].x;
a[0]=a[i];
a[i]=a[1];
a[1]=a[0];
}
else if(a[i].y==min&&a[i].x<min1)
{ min1=a[i].x;
a[0]=a[i];
a[i]=a[1];
a[1]=a[0];
}
}
sort(2,n);
s[u]=1;
for(i=2;i<=n;i++)
{ while(u>1&&sgn(a[s[u-1]],a[s[u]],a[i])==-1)
u--;
s[++u]=i;
}
fprintf(stdout,"%d\n",u);
for(i=1;i<=u;i++)
{ fprintf(stdout,"%.6f %.6f\n",a[s[i]].x,a[s[i]].y);
}
fin.close();
return 0;
}