Cod sursa(job #704147)

Utilizator Catah15Catalin Haidau Catah15 Data 2 martie 2012 16:34:14
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

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

double X[maxN], Y[maxN];
vector <int> P, st;
vector <int> :: iterator it;
int start;


long double sign (int A, int B, int C)
{
	return (long double) 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);
	
	start = 0;
	X[0] = 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 (start == i) continue;
		P.PB (i);
	}
	
	sort (P.begin(), P.end(), cmp);
	
	st.PB (start);
	
	for (unsigned i = 0; i < P.size(); ++ i)
	{
		while (st.size() >= 2)
		{
			int sz = st.size();
			
			if (sign (st[sz - 2], st[sz - 1], P[i]) <= 0) break;
			
			st.pop_back();
		}
		
		st.PB (P[i]);
	}
	
	printf ("%d\n", st.size());
	for (it = st.end() - 1; it != st.begin() - 1; -- it) printf ("%lf %lf\n", X[*it], Y[*it]);
	
	return 0;
}