Pagini recente » Cod sursa (job #888849) | Cod sursa (job #620444) | Cod sursa (job #335487) | Cod sursa (job #2202720) | Cod sursa (job #1528818)
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in"); ofstream g("infasuratoare.out");
const int Nmax=120000;
float X[Nmax],Y[Nmax];
int N,H,Viz[Nmax],Q[Nmax];
int main()
{ f>>N;
int i;
X[0]=Y[0]=1000000000;
for(i=1;i<=N;++i) f>>X[i]>>Y[i];
int Pinitial=0;
for(i=1;i<=N;++i)
if(X[i]<X[Pinitial]) Pinitial=i;
int w=1,Pcurent=Pinitial;
float last=0;
while(w || Pinitial != Pcurent)
{ w=0;
Q[++H]=Pcurent;
float Umax=10000;
int Pmax=Pcurent;
for(i=1;i<=N;++i)
if(!Viz[i] and i!=Pcurent)
{ float unghi=atan2((X[i]-X[Pcurent]),Y[i]-Y[Pcurent]);
if(unghi<0) unghi+=2*M_PI;
unghi-=last;
if(unghi<0) unghi+=2*M_PI;
if(Umax>unghi) {Umax=unghi; Pmax= i;}
}
last=atan2(-(X[Pcurent]-X[Pmax]),-(Y[Pcurent]-Y[Pmax]));
if(last<0) last+=2*M_PI;
Pcurent=Pmax;
Viz[Pcurent]=1;
}
reverse(Q+1,Q+H+1);
g<<H<<'\n';
for(i=1;i<=H;++i)g<<fixed<<setprecision(6)<<X[Q[i]]<<' '<<Y[Q[i]]<<'\n';
g.close(); return 0;
}