Pagini recente » Cod sursa (job #395073) | Cod sursa (job #2119935) | Cod sursa (job #2306442) | Cod sursa (job #1165212) | Cod sursa (job #1958067)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
vector <int> v;
int n, pm;
double x[120004], y[120004], mini = 1000000004;
bool viz[120004];
int main(){
fin>>n;
for(int i=1; i<=n; ++i){
fin>>x[i]>>y[i];
if(x[i]<mini){ mini = x[i]; pm = i; }
if(x[i]==mini && y[i]<y[pm]) pm = i;
}
double last=0;
bool mov=1;
int cur = pm;
while(mov || cur!=pm){
mov = 0;
v.push_back(cur);
int np=cur;
double ma = 100000;
for(int i=1; i<=n; ++i){
if(viz[i] || i==cur) continue;
double unghi = atan2(x[i]-x[cur],y[i]-y[cur]);
if(unghi<0) unghi+=2*M_PI;
unghi-=last;
if(unghi<0) unghi+=2*M_PI;
if(ma>unghi){ma = unghi; np = i;}
}
last = atan2(-(x[cur]-x[np]),-(y[cur]-y[np]));
if(last<0) last+=2*M_PI;
cur = np;
viz[cur] = 1;
}
fout<<v.size()<<'\n';
for(int i=v.size()-1; i>=0; --i) fout<<std::fixed<<std::setprecision(12)<<x[v[i]]<<" "<<y[v[i]]<<'\n';
return 0;
}