Cod sursa(job #534962)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 16 februarie 2011 17:06:45
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define eps 1e-12

int n,i,h;
typedef struct punct {
	double x,y;
};
punct p[120001],v[120001];
int s[120001],ok[120005];

inline int cmp1(double a,double b) {
	if (a+eps<b) return -1;
    if (b+eps<a) return 1;
    return 0;
}

bool cmp(const punct &a,const punct &b) {
	int t;
	t=cmp1(a.x,b.x);
	if (t!=0) return t==-1;
	return (cmp1(a.y,b.y)==-1);
}

int semn(punct a,punct b,punct c) {
	double A,B,C;
	A = a.y-b.y;
	B = b.x-a.x;
	C = a.x*b.y - b.x*a.y;
    return cmp1(A*c.x+B*c.y+C,0);
}

void rezolva() {
	int k,q;
	sort(v+1,v+n+1,cmp);
	ok[2]=1;
	s[1]=1; s[2]=2;
	k=2;
	i=3;
	q=1;
	while (!ok[1]) {
		while (ok[i]) {
			if (i==n) q=-1;
			i+=q;
		}
		while (k>=2 && semn(v[s[k-1]],v[s[k]],v[i])==-1) {
			ok[s[k--]]=0;
		}
		s[++k]=i; 
		ok[i]=1;
	}
    h=k-1;
}

int main () {
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	for (i=1; i<=n; i++) 
		scanf("%lf%lf",&v[i].x,&v[i].y);
	rezolva();
	printf("%d\n",h);
	for (i=2; i<=h+1; i++) 
		printf("%lf %lf\n",v[s[i]].x,v[s[i]].y);
	return 0;
}