Cod sursa(job #379595)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 2 ianuarie 2010 17:25:45
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
#define NMAX 120005
#define INF 2000000000
double X[NMAX], Y[NMAX];
int p[NMAX], st[NMAX];
int n, pi;
int comp(int i1,int i2){
	return ((double)((Y[i1]-Y[pi]) * (X[i2] - X[pi])) < ((double)(X[i1] - X[pi]) * (Y[i2] - Y[pi]))); 
}
double semn(int i1,int i2,int i3){
	return X[i1]*(Y[i2] - Y[i3]) + X[i2]*(Y[i3] - Y[i1]) + X[i3]*(Y[i1] - Y[i2]);
}
int main(){
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
	scanf("%d", &n);
	int i;
	X[0] = Y[0] = INF;
	for(i = 1; i <= n; ++i){
		scanf("%lf%lf", &X[i], &Y[i]);
		if(X[i] < X[pi] || (X[i] == X[pi] && Y[i] < Y[pi])) pi = i;
	}
	for(i = 1; i <= n; ++i)
		if(i != pi)
			p[++p[0]] = i;
	sort(p + 1, p + p[0] + 1,comp);
	st[++st[0]] = pi;
	for(i = 1; i <= p[0]; ++i){
		while(p[0] >= 3 && semn(st[st[0]-1],st[st[0]],p[i]) < 0 ) st[0] --;
		st[++st[0]] = p[i];
	}
	printf("%d\n",st[0]);
	for(i = 1; i <= st[0]; ++i)
		printf("%lf %lf\n",X[st[i]], Y[st[i]]);
	return 0;
}