Cod sursa(job #407304)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 2 martie 2010 11:08:58
Problema Infasuratoare convexa Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
#define NMAX 120010
struct pct{
	double x, y;};
pct v[NMAX];
int n, st[NMAX], f[NMAX];
struct cmp{
	bool operator()(const pct &a,const pct &b){
		if(a.y == b.y) return a.x > b.x;
		return a.y < b.y;
	}
};
int semn(pct a, pct b, pct c){
	double r = a.x*(b.y - c.y) + b.x*( c.y - a. y) + c.x * ( a.y - b. y);
	if(r > 0) return 1;
	if(r < 0) return -1;
	return 0;
}
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", &v[i].x, &v[i].y);
	sort(v + 1, v + n + 1, cmp());
	int k = 0;
	for(int i = 1; i <= n; ++i){
		while(k > 2 && semn(v[st[k-1]], v[st[k]], v[i]) < 0 ){
			f[st[k]] --;
			k--;
		}
		f[i]++;
		st[++k] = i;
	}
	for(int i = n ; i ; --i){
		if(f[i]) continue;
		while(k > 2 && semn(v[st[k-1]], v[st[k]], v[i]) < 0){
			f[st[k]]--;
			k--;
		}
		f[i]++;
		st[++k] = i;
	}
	printf("%d\n", k);
	for(int i = 1; i <= k; ++i)
		printf("%lf %lf\n", v[st[i]].x, v[st[i]].y);
}