Cod sursa(job #591164)

Utilizator Catah15Catalin Haidau Catah15 Data 22 mai 2011 20:13:58
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <vector>
#include <deque>

using namespace std;

#define LD long double
#define PB push_back
#define maxN 120005
#define inf (1 << 30)

double X[maxN], Y[maxN];
vector <int> pct;
deque <int> stiva;
int start;


LD sign (int A, int B, int C)
{
	return (LD) X[A] * Y[B] + X[B] * Y[C] + X[C] * Y[A] - Y[A] * X[B] - Y[B] * X[C] - Y[C] * X[A];
}


inline int cmp (int A, int B)
{
	LD x1 = X[A], y1 = Y[A];
	LD x2 = X[B], y2 = Y[B];
	
	return (double) (x1 - X[start]) * (y2 - Y[start]) < (double) (y1 - Y[start]) * (x2 - X[start]);
}


int main()
{
	freopen ("infasuratoare.in", "r", stdin);
	freopen ("infasuratoare.out", "w", stdout);
	
	int N;
	
	scanf ("%d", &N);
	
	X[0] = inf, Y[0] = inf;
	
	for (int i = 1; i <= N; ++ i)
	{
		scanf ("%lf %lf", &X[i], &Y[i]);
		
		if (X[i] == X[start] && Y[i] < Y[start]) start = i;
		if (X[i] < X[start]) start = i;
	}
	
	
	for (int i = 1; i <= N; ++ i)
	{
		if (i == start) continue;
		
		pct.PB (i);
	}
	
	
	sort (pct.begin(), pct.end(), cmp);
	
	
	stiva.PB (start);
	
	for (unsigned int i = 0; i < pct.size(); ++ i)
	{
		if (pct[i] == start) continue;
		
		for ( ; stiva.size() >= 2 && sign (stiva[stiva.size() - 2], stiva[stiva.size() - 1], pct[i]) > 0; ) stiva.pop_back();
		
		stiva.PB (pct[i]);
	}
	

	printf ("%d\n", stiva.size());
	
	for (int i = stiva.size() - 1; i >= 0; -- i) printf ("%lf %lf\n", X[stiva[i]], Y[stiva[i]]);
	
	
	return 0;
}