Pagini recente » Borderou de evaluare (job #508210) | Borderou de evaluare (job #1738188) | Borderou de evaluare (job #966728) | Borderou de evaluare (job #242006) | Cod sursa (job #1820296)
#include <fstream>
#include <math.h>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct a{
double x,y;
}
v[120001];
int i,n,viz[120001];
int infas[120001];
bool comparare (a lhs,a rhs){return lhs.y<rhs.y;}
bool comparare2 (a lhs,a rhs){return lhs.x<rhs.x;}
int main()
{
fin>>n;
for(i=1;i<=n;++i)
fin>>v[i].x>>v[i].y;
int punct_initial=1;
int curent=0;
for(i=1;i<=n;++i)
if(v[i].x<v[punct_initial].x)
punct_initial=i;
int miscare=1;
curent=punct_initial;
double last=0;int k=0;
while(miscare||punct_initial!=curent)
{
miscare=0;
double ma=10000;
infas[++k]=curent;
int poznoua=curent;
for(i=1;i<=n;++i)
{
if(viz[i]||i==curent)continue;
double unghi=atan2((v[i].x-v[curent].x),v[i].y-v[curent].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[curent].x-v[poznoua].x),-(v[curent].y-v[poznoua].y));
if(last<0)
last+=2*M_PI;
curent=poznoua;
viz[curent]=1;
}
fout<<k<<"\n";
for(i=k;i>=1;--i)
fout<<setprecision(6)<<fixed<<v[infas[i]].x<<" "<<v[infas[i]].y<<"\n";
return 0;
}