Cod sursa(job #599922)

Utilizator dspMihaiDespotovici Mihai dspMihai Data 29 iunie 2011 23:39:14
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.36 kb
#include <stdio.h>
#include <math.h>
#define PI 3.14159265
using namespace std;
long i,N,P,u;
double aux,X[120001],Y[120001],polar[120001];
long stiva[120001];


void swap (double x, double y)
{
	//SCHIMBARE 2 VALORI INTRE ELE
	double aux;
	
}
double unghi_polar (long pct)
{
	// CALCULEAZA VALOAREA UNGHIULUI POLAR
	double a,b,c;
	a=sqrt(X[pct]*X[pct]+(Y[P]-Y[pct])*(Y[P]-Y[pct]));
	b=sqrt((X[pct]-X[P])*(X[pct]-X[P])+(Y[pct]-Y[P])*(Y[pct]-Y[P]));
	c=X[P];
	return acos((b*b+c*c-a*a)/(2*b*c))*180/PI;
}


void sort_polar (double x[], double y[], double pol[], long prim, long ultim)
{
	// SORTAREA IN FUNCTIE DE UNGHIUL POLAR
	long min=prim,max=ultim;
	double aux,separator_lista=pol[(prim+ultim)/2];
	
	do
	{
		while (pol[min]<separator_lista) min++;
		while (pol[max]>separator_lista) max--;
		if (min<=max) 
		{
			aux=x[min];
			x[min]=x[max];
			x[max]=aux;
			aux=y[min];
			y[min]=y[max];
			y[max]=aux;
			aux=pol[min];
			pol[min]=pol[max];
			pol[max]=aux;
			min++; max--;
		}
	}
	while (min<=max);
	if (prim<max) sort_polar(x,y,pol,prim,max);
	if (min<ultim) sort_polar(x,y,pol,min,ultim);
	
}

bool verificare (long p1,long p2,long p3)
{
	// VERIFICA INTOARCEREA LA STANGA SAU DREAPTA ???
	if ((X[p2]-X[p1])*(Y[p3]-Y[p1])-(Y[p2]-Y[p1])*(X[p3]-X[p1])<0) return 1;
	else return 0;
}
int main ()
{
	// CITIRE
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
	scanf("%d", &N);
	scanf("%lf %lf", &X[1], &Y[1]);
	P=1;
	for (i=2; i<=N; i++) 
	{
		scanf("%lf %lf", &X[i], &Y[i]);
		if (Y[P]>Y[i]) P=i;
		else if (Y[P]==Y[i] && X[P]>X[i]) P=i;
	}
	// PUNE PUNCTUL INITIAL PE PRIMA POZITIE IN LISTA PUNCTELOR
	aux=X[1];
	X[1]=X[P];
	X[P]=aux;
	aux=Y[1];
	Y[1]=Y[P];
	Y[P]=aux;
	P=1;
	
	for (i=2; i<=N; i++) polar[i]=unghi_polar(i); //CALCULEAZA UNGHIURILE POLARE
	sort_polar(X,Y,polar,2,N); // SORTARE DUPA UNGHIURI POLARE
	// INCEPUT STIVA
	stiva[1]=1;
	stiva[2]=2;
	u=2;
	//INFASURATOARE CONVEXA
	for (i=3; i<=N; i++)
	{
		while (!verificare (stiva[u-1],stiva[u],i)) u--;
		stiva[++u]=i;
	}
	
	//VERIFICARI
	//printf("%d\n", P);
	//for (i=1; i<=N; i++) printf("%lf %lf %lf\n", X[i], Y[i], polar[i]);
	
	
	//AFISARE
	printf("%d\n",u);
	printf("%lf %lf\n", X[stiva[1]],Y[stiva[1]]);
	for (i=u; i>=2; i--) printf("%lf %lf\n", X[stiva[i]],Y[stiva[i]]);
	return 0;
}