Cod sursa(job #624063)

Utilizator the_snyper06FMI - ALexandru Mihai the_snyper06 Data 21 octombrie 2011 17:23:55
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.29 kb
#include<cstdio>
#include<cmath>

#define PI 3.14159265

using namespace std;

struct Point {
	
	double x ;
	double y ;
	double unghiPolar_A0;
	double dist_A0;
} ;

int n ;
Point L[120001] ;
Point startPoint ;
Point st[120001] ;

void Citire()
{
	int i ;
	
	scanf("%d", &n) ; // citesc numarul de puncte
	for(i = 1; i <= n; i++)
		scanf("%lf %lf", &L[i].x, &L[i].y) ; // citesc coordonatele punctelor
}

inline double Distanta(Point A, Point B)
{
	return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y)) ;
}

inline double UnghiPolar(Point A, Point B)
{
	Point C = {B.x, A.y} ;
	double AB, AC, BC ;
	double cosA, acosA ;
	
	if(A.x == B.x && A.y == B.y) return -200 ;
	if(A.x == B.x) return 90 ;
	if(A.y == B.y) return 180 ;
	\
	AB = Distanta(A, B) ;
	AC = Distanta(A, C) ;
	BC = Distanta(B, C) ;
	
	cosA = (AB * AB + AC * AC  - BC * BC) / (2 * AB * AC) ;	
	acosA = acos(cosA) * 180.0 / PI;
	
	if(A.y > B.y) acosA += 180 ;	
	else acosA = 180 - acosA ;
	
	return acosA ;
}

inline bool UnghiIntoarcere(Point A, Point B, Point C) // verific daca unghiul de intoarcere e spre stanga
{
	double S = A.x * B.y + B.x * C.y + A.y * C.x - B.y * C.x - A.x * C.y - B.x * A.y ;
	return (S > 0) ;
}

Point InitializarePunctStart() // calculez punctul de start
{
	int i;
	Point punctStart = L[1] ;
	
	for(i = 2; i <= n; i++)
		if(L[i].x > punctStart.x) punctStart = L[i] ;
		else if(L[i].x == punctStart.x && L[i].y < punctStart.y) punctStart = L[i] ;
	
	return punctStart ;
}

void Afisare(int n)
{
	int i;
	
	for(i = 1; i <= n; i++)
		printf("%.12lf \t %.12lf \t\t %.12lf \t\t %.12lf\n", L[i].x, L[i].y, L[i].unghiPolar_A0, L[i].dist_A0);
	printf("\n------\n\n");
}


void SorteazaPuncteDupaUnghiPolar(Point startPoint)
{
	int i, j, m ;
	Point aux ;
	
	L[0] = startPoint ;
	for(i = 1; i <= n; i++)
	{
		L[i].unghiPolar_A0 = UnghiPolar(L[0], L[i]) ;
		L[i].dist_A0 = Distanta(L[0], L[i]) ;
	}
	
	//Afisare(n);
	
	for(i = 1; i <= n; i++)
		for(j = 1; j <= n; j++)
			if(L[i].unghiPolar_A0 < L[j].unghiPolar_A0)
			{
				aux = L[i];
				L[i] = L[j];
				L[j] = aux;
			}
			
	//Afisare(n);
			
	Point P[201] ;
	m = 2 ; P[1] = startPoint ;	
	for(i = 1; i <= n; i++)
		if(L[i].unghiPolar_A0 >= -180 ) P[m++] = L[i];
	
	m--;
	n = 3;
	L[1] = P[1];
	L[2] = P[2];
	for(i = 3; i <= m; i++)
		if(P[i - 1].unghiPolar_A0 != P[i].unghiPolar_A0) L[n++] = P[i];
		else if(P[i - 1].dist_A0 < P[i].dist_A0)
		{
			n--;
			L[n++] = P[i];
		}
	n--;
	
	//Afisare(n);
}

void Calcul()
{
	int i, top = 3;
	
	st[0] = L[1];
	st[1] = L[2];
	st[2] = L[3];
	
	for(i = 4; i <= n && top >= 2; i++)
	{
		Point a = L[i];
		Point b = st[top - 1];
		Point c = st[top - 2];
		
		if(!UnghiIntoarcere(c, b, a))
		{
			top--;
			st[top++] = a;
		}
		else st[top++] = a;
	}
	
	printf("%d\n", top);
	for(i
		= 0; i < top; i++)
		printf("%.12lf \t\t %.12lf\n", st[i].x, st[i].y);
}

int main()
{
	freopen("infasuratoare.in", "r", stdin) ;
	freopen("infasuratoare.out", "w", stdout) ;
	
	Citire() ; // citire date de intrare
	//printf("%d\n", UnghiIntoarcere((Point){1, 1}, (Point){2, 1}, (Point){3, 3})) ;
	
	startPoint = InitializarePunctStart(); // punctul de start	
	SorteazaPuncteDupaUnghiPolar(startPoint);
	
	Calcul();
	
	return 0 ;
}