Pagini recente » Cod sursa (job #3173953) | Cod sursa (job #1917596) | Cod sursa (job #2500764) | Cod sursa (job #220945) | Cod sursa (job #608770)
Cod sursa(job #608770)
#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 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";
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));
}