Pagini recente » Cod sursa (job #2784544) | Cod sursa (job #223763) | Cod sursa (job #704089) | Cod sursa (job #2017716) | Cod sursa (job #728864)
Cod sursa(job #728864)
#include<fstream>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#define maxn 120010
#define pb push_back
#define mp make_pair
#define pi 3.1415
using namespace std;
ifstream in("infasuratoare.in");
vector<pair<double,double> > vec;
vector<int> rasp;
int N;
void read()
{
in>>N;
for(int i=1;i<=N;i++)
{
double x,y;
in>>x>>y;
vec.pb(mp(x,y));
}
}
int main()
{
int i,origine=0;
read();
for(i=0;i<(int)vec.size();i++)
{
if(vec[i].second<vec[origine].second) origine=i;
else
if(vec[i].second==vec[origine].second)
if(vec[i].first<vec[origine].first)
origine=i;
}
int poz=origine;
bool prima=true,parc[maxn];
double rest=0;
for(i=0;i<=N;i++)
parc[i]=false;
while(prima == true || poz!=origine)
{
prima=false;
double minim=1<<30;
int posib=poz;
rasp.pb(poz);
for(i=0;i<N;i++)
{
if(parc[i]==true || i==poz) continue;
double unghi=atan2((vec[i].second-vec[poz].second),(vec[i].first-vec[poz].first));
if(unghi<0) unghi+=2*pi;
unghi-=rest;
if(unghi<0) unghi+=2*pi;
if(unghi<minim)
{
minim=unghi;
posib=i;
}
}
rest=atan2((vec[posib].first-vec[poz].first),(vec[posib].second-vec[poz].second));
if(rest<0) rest+=2*pi;
poz=posib;
parc[poz]=true;
}
freopen("infasuratoare.out","w",stdout);
for(i=0;i<(int)rasp.size();i++)
printf("%lf %lf\n",vec[rasp[i]].first,vec[rasp[i]].second);
return 0;
}