Cod sursa(job #250970)

Utilizator raduzerRadu Zernoveanu raduzer Data 1 februarie 2009 14:54:04
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define x first
#define y second

typedef pair < double, double > pd;

const int MAX_N = 120010;

int n;
pd a[MAX_N];
int s[MAX_N];
char f[MAX_N];

int sign(pd a, pd b, pd c)  
{  
    return ((a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y) <= 0) ? 0 : 1;  
}  

int main()
{
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
	
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%lf %lf", &a[i].x, &a[i].y);
	
	sort(a + 1, a + n + 1);
	
	s[s[0] = 1] = 1;
	for (int i = 2, p = 1; i; i += (p = (i == n) ? -p : p))
		if (!f[i])
		{
			while (s[0] > 1 && sign(a[i], a[s[s[0]]], a[s[s[0] - 1]]))
				f[s[s[0]--]] = 0;
			f[s[++s[0]] = i] = 1;
		}
	
	printf("%d\n", s[0] - 1);
	for (int i = 1; i < s[0]; ++i) printf("%.6f %.6f\n", a[s[i]].x, a[s[i]].y);
}