Cod sursa(job #608769)

Utilizator cosminx2003Cosmin Clapon cosminx2003 Data 17 august 2011 22:46:34
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream.h>
#include <fstream.h>
#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;

	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));
}