Pagini recente » Cod sursa (job #1077156) | Cod sursa (job #2639449) | Cod sursa (job #1564771) | Cod sursa (job #2620685) | Cod sursa (job #2142416)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <climits>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{
double x,y;
}v[120001];
int compare (punct A,punct B)
{
if(A.x==B.x)return(A.y<B.y);
return (A.x<B.x);
}
double poz1,last,poz2,maxim,minim,minim1,X,P1,P2;
int n,i,t,P,POZ,Q,fv[120001],V[120001],ok,q;
int main()
{
minim=INT_MAX;minim1=INT_MAX;
f>>n;
for(i=1;i<=n;i++)
{
f>>v[i].x>>v[i].y;
if(v[i].x<minim){minim=v[i].x;minim1=v[i].y;POZ=i;}
else if(v[i].x==minim){if(v[i].y<minim1){minim1=v[i].y;POZ=i;}}
}
ok=1;
P=POZ;
t=1;
V[1]=P;
while(ok)
{
minim=INT_MAX;maxim=INT_MIN;
q=POZ;
for(i=1;i<=n;i++)
{
if(i==POZ)continue;
if(fv[i]==0)
{
X=atan2(v[i].x-v[POZ].x,v[i].y-v[POZ].y);
if(X<0)X=X+2*M_PI;
X=X-last;
if(X<0)X=X+2*M_PI;
if(X<minim){minim=X;q=i;}
}
}
last=atan2(v[q].x-v[POZ].x,v[q].y-v[POZ].y);
if(last<0)last=last+2*M_PI;
POZ=q;fv[POZ]=1;
if(P==POZ){ok=0;break;}
t++;
V[t]=POZ;
}
g<<t<<'\n';
for(i=t;i>=1;i--)
{
g<<fixed<<setprecision(6)<<v[V[i]].x<<" ";
g<<fixed<<setprecision(6)<<v[V[i]].y<<'\n';
}
return 0;
}