Cod sursa(job #608772)

Utilizator cosminx2003Cosmin Clapon cosminx2003 Data 17 august 2011 23:12:05
Problema Infasuratoare convexa Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2 kb
#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;
}