Cod sursa(job #385852)

Utilizator blasterzMircea Dima blasterz Data 23 ianuarie 2010 16:41:17
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#define N 121000

using namespace std;

struct nod
{
	double x, y;
	bool operator < (const nod &a) const
	{
		if(x < a.x) return 1;
		if(x == a.x && y < a.y) return 1;
		return 0;
	}
};

nod a[N];
int n;
nod LS[N], LI[N];
int ns, ni;

void read()
{
	freopen("infasuratoare.in","r",stdin);
	scanf("%d\n", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%lf %lf\n", &a[i].x, &a[i].y);
}

inline int isleft(nod p0, nod p1, nod p2)
{
	double x = (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
	if(fabs(x - 0) < 1e-10) return 0;
	if(x < 0) return -1;
	if(x > 0) return 1;
}

void solve()
{
	sort(a+1,a+n+1);
	
	LS[++ns] = a[1];
	LS[++ns] = a[2];

	int i;

	for(i = 3; i <= n; ++i)
	{
		while(ns > 2 && isleft(a[i], LS[ns], LS[ns - 1]) < 0) 
			--ns;
		LS[++ns] = a[i];
	}

	
	LI[++ni] = a[n];
	LI[++ni] = a[n-1];

	for(i = n - 2; i >= 1; --i)
	{
		while(ni > 2 && isleft(a[i], LI[ni], LI[ni - 1]) < 0)
			--ni;
		LI[++ni] = a[i];
	}

	
	freopen("infasuratoare.out","w",stdout);

	printf("%d\n", ns + ni - 2);
	
	for(i = ns - 1; i ; --i)
		printf("%lf %lf\n", LI[i].x, LI[i].y);
	
	for(i = ni - 1; i ; --i)
		printf("%lf %lf\n", LS[i].x, LS[i].y);



}
int main()
{
	read();
	solve();
	return 0;
}