Pagini recente » Cod sursa (job #7994) | Cod sursa (job #182429) | Cod sursa (job #1031151) | Cod sursa (job #816641) | Cod sursa (job #1966569)
#include <fstream>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
struct
{
double x,y;
}v[120003];
int n,m,ap[120003],sol[120003],st,ok=1,act;
int main()
{
f>>n;
v[0].x=v[0].y=1000000000;
for(int i=1;i<=n;++i) f>>v[i].x>>v[i].y;
for(int i=1;i<=n;++i) if(v[i].x<v[st].x) st=i;
act=st;
double last=0;
while(ok||st!=act)
{
ok=0;
sol[++m]=act;
double ma=10000;
int poznoua=act;
for(int i=1;i<=n;++i)
{
if(ap[i]||i==act) continue;
double unghi=atan2((v[i].x-v[act].x),v[i].y-v[act].y);
if(unghi<0) unghi+=2*M_PI;
unghi-=last;
if(unghi<0) unghi+=2*M_PI;
if(ma>unghi) {ma=unghi;poznoua=i;}
}
last=atan2((v[poznoua].x-v[act].x),v[poznoua].y-v[act].y);
if(last<0) last+=2*M_PI;
act=poznoua;
ap[act]=1;
}
g<<m<<'\n';
for(int i=m;i>=1;--i) g<<fixed<<setprecision(6)<<v[sol[i]].x<<' '<<fixed<<setprecision(6)<<v[sol[i]].y<<'\n';
return 0;
}