Cod sursa(job #468678)

Utilizator blasterzMircea Dima blasterz Data 4 iulie 2010 16:28:45
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
using namespace std;

#include <cstdio>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <cmath>
#define eps 1e-12
#define N 121000

struct nod { double x,y; nod(){}; nod(double a, double b){ x=a; y=b;};};

nod a[N];
int n;
nod P;
nod st[N];
int ns;

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


struct cmp{
	bool operator()(const nod &a, const nod &b)const
	{
		int t=isleft(P, a, b);
		if(t == 1) return 1;
		return 0;
	}
};

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);
}

void solve()
{
	int i;
	int poz=-1;
	P=nod(0x3f3f3f3f, 0x3f3f3f3f);
	
	for(i=1;i<=n;++i)
		if(a[i].y < P.y) P=a[i], poz=i;
		else if(a[i].y == P.y && a[i].x < P.x) P=a[i], poz=i;
		
	nod t=a[poz]; a[poz]=a[1]; a[1]=t;
	
	stable_sort(a+2,a+n+1, cmp());
	
	//for(i=1;i<=n;++i)printf("%lf %lf\n", a[i].x, a[i].y);
	
	st[++ns]=a[1];
	st[++ns]=a[2];
//	st[++ns]=a[3];
	
	for(i=3;i<=n;++i)
	{
		while(ns > 2 && isleft(st[ns-1], st[ns], a[i]) == -1) --ns;
		st[++ns]=a[i];
	}
	
	
	freopen("infasuratoare.out","w",stdout);
	printf("%d\n", ns);
	for(i=1;i<=ns;++i) printf("%lf %lf\n", st[i].x, st[i].y);
	
	
	
}
int main()
{
	read();
	solve();
	
	return 0;
}