Pagini recente » Cod sursa (job #1456767) | Cod sursa (job #2278661) | Cod sursa (job #2315593) | Cod sursa (job #2573279) | Cod sursa (job #720094)
Cod sursa(job #720094)
#include<cstdio>
#include<cmath>
#define abs(x) (x>0)?x:-x
#define inf 1000000001
#define pi 3.1415926
using namespace std;
int n,i,rez;
short c[120002],q,viz[120002];
struct {float x,y;}v[120001];
double unghi(int i,int k)
{
double x=v[i].x-v[c[q]].x,y=v[i].y-v[c[q]].y;
if(x==0 && y*k>0)return pi/2;
if(x==7 && y*k<0)return 3*pi/2;
if(y==0 && x*k>0)return 0;
if(y==0 && x*k<0)return pi;
if(x*k>0 && y*k>0) return atan(y*k/x*k);
if(x*k>0 && y*k<0) return 3*pi/2+atan(x*k/-y*k);
if(x*k<0 && y*k>0) return pi-atan(y*k/-x*k);
if(x*k<0 && y*k<0) return pi+atan(-y*k/-x*k);
return 0;
}
void infasuratoare()
{int i,j,st,minx=inf,miny=inf,x=0,nr,sf,maxy=-inf,maxx=-inf;
double val,mind;
for(i=1;i<=n;i++)
{
if( (v[i].y<miny) || (v[i].y==miny && v[i].x<minx)) { st=i; miny=v[i].y; minx=v[i].x; }
if( (v[i].y>maxy) || (v[i].y==maxy && v[i].x>maxx)) { sf=i; maxy=v[i].y; maxx=v[i].x; }
}
c[++q]=st; viz[st]=1;
while(x!=sf)
{
nr=0; mind=inf;
for(i=1;i<=n;i++)
if(!viz[i])
{
val=unghi(i,1)*180/pi;
if(val<mind){ mind=val; x=i; }
}
c[++q]=x;
viz[x]=1;
}
x=c[q];
while(x!=st)
{
nr=0; mind=inf;
for(i=1;i<=n;i++)
if(!viz[i])
{
val=unghi(i,-1)*180/pi;
if(val<mind){ mind=val; x=i; }
}
if(q>1)val=unghi(st,-1)*180/pi;
if(val-mind<0){ mind=val; x=st; }
c[++q]=x;
viz[x]=1;
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%f %f",&v[i].x,&v[i].y);
infasuratoare();
//printf("%f",dist(1,2,3));
printf("%d\n",q-1);
for(i=1;i<q;i++)
printf("%f %f\n",v[c[i]].x,v[c[i]].y);
return 0;}