Pagini recente » Cod sursa (job #2490193) | Cod sursa (job #3003194) | Cod sursa (job #452773) | Cod sursa (job #2349623) | Cod sursa (job #608772)
Cod sursa(job #608772)
#include <iostream.h>
#include <fstream.h>
#include <iomanip>
#include <math.h>
#define PI 3.14159265
#define MAX 120000
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
using namespace std;
struct point
{
double x,y;
bool ok;
};
point P[MAX];
int V[MAX];
double unghi(point p0,point p1,point p2);
int rev(int nr);
int main()
{
int n,i,poz,nr,mov=0;
point curr,min,pre;
double panta,aux;
g<< setprecision(12);
f>>n;
for(i=1;i<=n;i++)
f>>P[i].x>>P[i].y;
min.x=P[1].x;
for(i=1;i<=n;i++)
if(P[i].x<min.x)
min.x=P[i].x, min.y=P[i].y, poz=i;
/*for(i=1;i<=n;i++)
if(P[i].x==min.x&&poz!=i&&P[i].y<min.y)
poz=i;*/
curr.x=P[poz].x, curr.y=P[poz].y;
pre.x=0;
pre.y=0;
nr=1;
V[nr++]=poz;
do
{
panta=8;
mov=0;
for(i=1;i<=n;i++)
{
if(!P[i].ok)
{
aux=unghi(pre,curr,P[i]);
if(panta>=aux)
panta=aux, poz=i, mov=1;
}
}
pre.x=curr.x, pre.y=curr.y;
curr.x=P[poz].x, curr.y=P[poz].y;
P[poz].ok=true, V[nr++]=poz;
} while((curr.x!=min.x||curr.y!=min.y)&&mov);
g<<--nr-1<<"\n";
if(rev==0)
for(i=nr-1;i>=1;i--)
g<<P[V[i]].x<<" "<<P[V[i]].y<<"\n";
else
for(i=1;i<nr;i++)
g<<P[V[i]].x<<" "<<P[V[i]].y<<"\n";
f.close();
g.close();
return 0;
}
double unghi(point p0,point p1,point p2)
{
double d0,d1,d2;
d0=sqrt((p1.x-p0.x)*(p1.x-p0.x)+(p1.y-p0.y)*(p1.y-p0.y));
d1=sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
d2=sqrt((p2.x-p0.x)*(p2.x-p0.x)+(p2.y-p0.y)*(p2.y-p0.y));
return 2*PI-acos((d1*d1+d0*d0-d2*d2)/(2*d1*d0));
}
int rev(int nr)
{
int i,j,k;
int count = 0;
double z;
if (nr < 3)
return(0);
for (i=1;i<nr;i++)
{
j = (i + 1) % nr;
k = (i + 2) % nr;
z = (P[V[j]].x - P[V[i]].x) * (P[V[k]].y - P[V[j]].y);
z -= (P[V[j]].y - P[V[i]].y) * (P[V[k]].x - P[V[j]].x);
if (z < 0)
count--;
else if (z > 0)
count++;
}
if (count > 0)
return 1;
else if (count < 0)
return 0;
}