Cod sursa(job #624238)

Utilizator the_snyper06FMI - ALexandru Mihai the_snyper06 Data 22 octombrie 2011 02:26:58
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include<cstdio>
#include<algorithm>
#define infinit (1<<29)

using namespace std;

struct Punct { double x, y, panta; };

long n;
Punct L[120001], P[120001], punctStart;

inline double Determinant(Punct A, Punct B, Punct C)
{ return (A.x * B.y + B.x * C.y + A.y * C.x - B.y * C.x - A.x * C.y - B.x * A.y); }

inline bool cmp(Punct A, Punct B)
{ return (A.panta < B.panta); }

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

void Citire()
{
	long i;
	
	punctStart = (Punct){-1000000001, -1000000001};
	
	freopen("infasuratoare.in", "r", stdin);
		scanf("%ld", &n);
		for(i = 1; i <= n; i++)
		{
			scanf("%lf %lf", &L[i].x, &L[i].y);
			if(L[i].x > punctStart.x) punctStart = L[i];
			else if(L[i].x == punctStart.x && L[i].y < punctStart.y) punctStart = L[i];
		}
	fclose(stdin);
}

void Calcul()
{
	long i, m = 0, top = 1;
	
	P[++m] = punctStart; 
	for(i = 1; i <= n; i++)
		if(L[i].x != punctStart.x || L[i].y != punctStart.y)
		{			
			L[i].panta = punctStart.x == L[i].x ? -infinit : (punctStart.y - L[i].y) / (punctStart.x - L[i].x);
			P[++m] = L[i]; // adaug punctele pentru sortare
		}

	sort(P + 2, P + m + 1, cmp); // sortez punctele in functie de panta
	
	n = 1;
	L[1] = P[1];
	for(i = 2; i <= m; i++)
	{
		if(L[n].panta != P[i].panta) L[++n] = P[i];
		else if(Distanta(L[1], L[n]) < Distanta(L[1], P[i])) L[n] = P[i];
	}
	
	for(i = 1; i <= n; i++)
	{
		while(top > 2 && Determinant(P[top - 2], P[top - 1], L[i]) < 0) 
		{
			top--;
		}
		P[top++] = L[i];
	}
	top--;
	n = top;
}

int main()
{	
	int i;
	
	Citire(); // citire
	Calcul();
	freopen("infasuratoare.out", "w", stdout);
		printf("%ld\n", n);
		for(i = 1; i <= n; i++) printf("%.6lf %.6lf\n", P[i].x, P[i].y);
	fclose(stdout);
	
	return 0;
}