Pagini recente » Cod sursa (job #282263) | Cod sursa (job #1532018) | Formatare Textile | Cod sursa (job #1856925) | Cod sursa (job #1373560)
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
#define NN 120008
#define PI 3.14159265
using namespace std;
struct nod{
double x;
double y;
}a[NN];
vector <int> c;
vector <int>::iterator it;
double unghi,maxu,u;
bool ok,use[NN];
int n,o,i,start,poz;
int main()
{
freopen("infasuratoare.in", "r",stdin);
freopen("infasuratoare.out", "w",stdout);
scanf("%d",&n);
o=1;
for(i=1;i<=n;i++){
scanf("%lf%lf",&a[i].x,&a[i].y);
if (a[i].x<a[o].x)o=i;
else if (a[i].x==a[o].x && a[i].y<a[o].y)o=i;
}
start=o;
ok=true;
while(ok || start!=o){
ok=false;
c.push_back(o);
maxu=10000;
for(i=1;i<=n;i++)
if(use[i]==false && i!=o){
unghi=atan2((a[i].x-a[o].x),(a[i].y-a[o].y));
if (unghi<0)unghi+= 2*PI;
unghi-=u;
if(unghi<0)unghi+= 2*PI;
if (maxu>unghi){
poz=i;
maxu=unghi;
}
}
u=atan2(-(a[o].x-a[poz].x),-(a[o].y-a[poz].y));
if (u<0)u+=2*PI;
o=poz;
use[o]=true;
}
printf("%d\n",c.size());
reverse(c.begin(),c.end());
for(it=c.begin();it!=c.end();++it)
printf("%f %f\n",a[*it].x,a[*it].y);
return 0;
}