Cod sursa(job #886737)

Utilizator DanutsDanut Rusu Danuts Data 23 februarie 2013 10:46:31
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<stdio.h>
#include<algorithm>

using namespace std;

#define esp 1e-12
#define max_n 120001

struct punct{double x,y;};

punct v[max_n],p[max_n];
int ok[max_n],s[max_n];

int n,h;
int cmp1(double a,double b){
	if(a+esp<b) return 1;
	if(b+esp<a) return -1;
	return 0;
}
bool cmp(const punct &a,const punct &b){
	int 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){
	int 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 convex(){
	sort(v+1,v+n+1,cmp);
	int k=2,q,i=3;
	s[1]=1;s[2]=2;
	ok[2]=1;
	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(int i=1;i<=n;i++)
		scanf("%lf %lf",&v[i].x,&v[i].y);
	convex();
	printf("%d\n",h);
	for(int i=h;i>=1;i--)
		printf("%lf %lf\n",v[s[i]].x,v[s[i]].y);
	return 0;
}