Pagini recente » Cod sursa (job #1377388) | Cod sursa (job #1218174) | Cod sursa (job #2151729) | Cod sursa (job #2080370) | Cod sursa (job #2351032)
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iomanip>
using namespace std;
vector<int> v;
double x[120000],y[120000];
int n,verif[120000];
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int main()
{
f>>n;
x[0]=1000000000;
y[0]=1000000000;
for(int i=1;i<=n;++i)
f>>x[i]>>y[i];
int pi=0,pc=0,go=1;
for(int i=1;i<=n;++i)
if(x[i]<x[pi])
pi=i;
pc=pi;
double u=0;
while(go!=0 or pi!=pc)
{
go=0;
v.push_back(pc);
double ma=10000;
int poznoua=pc;
for(int i=1;i<=n;++i)
{
if(verif[i]!=0 or i==pc)
continue;
double unghi=atan2(x[i]-x[pc],y[i]-y[pc]);
if(unghi<0)
unghi=unghi+2*M_PI;
unghi=unghi-u;
if(unghi<0)
unghi=unghi+2*M_PI;
if(ma>unghi)
{
ma=unghi;
poznoua=i;
}
}
u=atan2(-(x[pc]-x[poznoua]),-(y[pc]-y[poznoua]));
if(u<0)
u=u+2*M_PI;
pc=poznoua;
verif[pc]=1;
}
reverse(v.begin(),v.end());
g<<v.size()<<endl;
g<<setprecision(6)<<fixed;
for(int i=0;i<v.size();++i)
g<<x[v[i]]<<" "<<y[v[i]]<<endl;
return 0;
}