Pagini recente » Cod sursa (job #398037) | Cod sursa (job #2526616) | Cod sursa (job #989256) | Cod sursa (job #2650637) | Cod sursa (job #2500711)
#include <iostream>
#include <algorithm>
#include <deque>
#include <cmath>
#include <fstream>
using namespace std;
const long double PI=3.141592653589793238;
const int nm=120003;
typedef struct pct{long double x,y;};
pct a[nm];
deque <int> v;
bool ok, ut[nm];//ut[i]=true daca pct i a fost folosit
long double u,z,unghi;//pt tot felul de unghiuri
int i,n,in,po,c;//in=inceput, c=pct. curent
int main()
{
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
fin>>n;
in=1;
for(i=1;i<=n;i++)fin>>a[i].x>>a[i].y;
for(i=2;i<=n;i++)
if((a[i].x<a[in].x)||((a[i].x==a[in].x)&&(a[i].y<a[in].y)))in=i;
c=in;//punctul curent e cel de inceput
u=0;
do
{
v.push_back(c);//punem pe c in lista punctelor de pe infas. conv
z=5000l;
for(i=1;i<=n;i++)
if((!ut[i])&&(i!=c))//daca nu am folosit inca punctul
{
unghi=atan2((a[i].x-a[c].x),(a[i].y-a[c].y));
if(unghi<0)unghi+=2*PI;
unghi-=u;
if(unghi<0)unghi+=2*PI;
if(z>unghi){z=unghi;po=i;}
}
u=atan2(-(a[c].x-a[po].x),-(a[c].y-a[po].y));
if(u<0)u+=2*PI;
c=po;//se actualizeaza pozitia
ut[c]=true;
}while(in!=c);//cat timp inceputul e diferit de nodul curent
reverse(v.begin(),v.end());
v.push_front(v.back());
v.pop_back();
fout<<v.size()<<"\n";
for(i=0;i<v.size();i++)
fout<<a[v[i]].x<<" "<<a[v[i]].y<<"\n";
return 0;
}