Cod sursa(job #343761)

Utilizator ancaaaancaaa ancaaa Data 27 august 2009 10:42:04
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
/*
	Infasuratoarea convexa - Scanarea Graham 
*/

#include <iostream>
#include <algorithm>

using namespace std;

#define N 120001

int n, ns;

struct nod {
	double x, y;
	nod() {}
	nod(double x1, double y1) {
		x=x1;
		y=y1;
	}
};

nod st[N], P(0x3f3f3f3f, 0x3f3f3f3f), a[N];

int isLeft(nod p0, nod p1, nod p2) {
	// determin poz lui p0 fata de dreapta p1p2
	// <0 este in partea stanga
	// =0 pe dreapta
	// >0 in partea dreapta
	double d = (p0.x-p1.x)*(p2.y-p1.y)-(p0.y-p1.y)*(p2.x-p1.x);
	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 0; // dc e pe partea dreapta => a<b
		return 1;
	}
};

int main() {
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);

	cin>>n;

	for (int i=1; i<=n; i++)
		cin>>a[i].x>>a[i].y;
	
	//caut cel mai de jos punct si cel mai din stanga
	int poz=0;
	for (int 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;

	// pun cel mai de jos si cel mai din stanga element pe prima poz
	nod t=a[1];
	a[1]=P;
	a[poz]=t;
	
	// ordonez vectorul crescator dupa unghiul polar
	sort(a+2, a+n+1,cmp());

	st[++ns]=a[1];
	st[++ns]=a[2];
	st[++ns]=a[3];

	for (int i=4; i<=n; i++) {
		while (isLeft(st[ns-1], st[ns], a[i])==1) --ns;
		st[++ns]=a[i];
	}
	
	cout<<ns<<endl;
	for (int i=1; i<=ns; i++)
		cout<<st[i].x<<" "<<st[i].y<<endl;

	return 0;
}