Cod sursa(job #406696)
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
struct coord
{
double x,y;
};
#define nn 120005
coord v[nn];
int z[nn],n,m;
int dir(coord A,coord B,coord C)
{
double det=A.x*B.y+B.x*C.y+C.x*A.y-C.x*B.y-B.x*A.y-A.x*C.y;
if(det==0)
return 0;
if(det<0)
return -1;
return 1;
}
int polare(coord A,coord B)
{
if(dir(v[1],A,B)>0)
return 1;
if(dir(v[1],A,B)<0)
return 0;
return(v[1].x-A.x)*(v[1].x-A.x)+(v[1].y-A.y)*(v[1].y-A.y) <
(v[1].x-B.x)*(v[1].x-B.x)+(v[1].y-B.y)*(v[1].y-B.y);
}
double directie(int a,int b,int c)
{
return (v[b].x-v[a].x)*(v[c].y-v[a].y)-(v[b].y-v[a].y)*(v[c].x-v[a].x);
}
int main()
{
ifstream fin("infasuratorare.in");
fin>>n;
for(int i=1;i<=n;++i)
fin>>v[i].x>>v[i].y;
int p=1;
for(int i=2;i<=n;++i)
if(v[p].x<v[i].x)
p=i;
else if(v[p].x==v[i].x)
if(v[p].y<v[i].y)
p=i;
z[++m]=p;
coord aux=v[1];
v[1]=v[p];
v[p]=aux;
cout<<z[1];cin.get();
//sort(v+2,v+n,polare);
int gata=0;
while(!gata)
{
for(int i=1;i<=n;++i)
if(z[m]!=i)
{
int pp=1;
for(int j=1;j<=n&&pp;++j)
if(i!=j&&j!=z[m])
if(directie(z[m],i,j)<0)
pp=0;
if(pp)
{
z[++m]=i;
break;
}
}
if(z[m]==z[1])gata=1;
}
FILE *f=fopen("infasuratoare.out","w");
fprintf(f,"%d\n",m);
for(int i=1;i<m;++i)
fprintf(f,"%f %f\n",v[z[i]].x,v[z[i]].y);
return 0;
}