Pagini recente » Cod sursa (job #472052) | Cod sursa (job #2922001) | Cod sursa (job #3218972) | Cod sursa (job #1009354) | Cod sursa (job #728870)
Cod sursa(job #728870)
#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].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].first-vec[poz].first),(vec[i].second-vec[poz].second));
if(unghi<0) unghi+=2*pi;
unghi-=rest;
if(unghi<0) unghi+=2*pi;
if(unghi<minim)
{
minim=unghi;
posib=i;
}
}
rest=atan2(-(vec[poz].first-vec[posib].first),-(vec[poz].second-vec[posib].second));
if(rest<0) rest+=2*pi;
poz=posib;
parc[poz]=true;
}
freopen("infasuratoare.out","w",stdout);
reverse(rasp.begin()+1,rasp.end());
printf("%d\n",(int)rasp.size());
for(i=0;i<(int)rasp.size();i++)
printf("%lf %lf\n",vec[rasp[i]].first,vec[rasp[i]].second);
return 0;
}