Cod sursa(job #560558)

Utilizator paul24090FMI - Balauru Paul paul24090 Data 18 martie 2011 16:15:27
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
#include <cstdio>
#include <math.h>

struct punct{
	double x,y,panta;
};
punct c[120006],c2[120006],s[120006];

int n,n2,ns;

void citire(){
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++)
		scanf("%lf %lf",&c[i].x,&c[i].y);
}

void detElemMin(){
	int i,minimi;
	punct minim,aux;
	minim=c[1];
	minimi=1;
	for(i=2;i<=n;i++)
		if(c[i].x<minim.x){
			minim=c[i];
			minimi=i;
		}
		else if(c[i].x==minim.x && c[i].y<minim.y){
			minim=c[i];
			minimi=i;
		}
	aux=c[1];
	c[1]=c[minimi];
	c[minimi]=aux;
}

void detPante(){
	int i;
	for(i=2;i<=n;i++){
		if(c[i].x==c[1].x)
			c[i].panta=2000000000;
		else c[i].panta=(c[i].y-c[1].y)/(c[i].x-c[1].x);
	}
}

int divide(int p,int q){
	int st=p,dr=q;
	punct aux=c[p];
	while(st<dr){
		while(st<dr && (c[dr].panta>aux.panta || (c[dr].panta==aux.panta && c[dr].x>aux.x) || (c[dr].panta==aux.panta && c[dr].x==aux.x && c[dr].y>=aux.y)))
			dr--;
		c[st]=c[dr];
		while(st<dr && (c[st].panta<aux.panta || (c[st].panta==aux.panta && c[st].x<=aux.x)|| (c[st].panta==aux.panta && c[st].x==aux.x && c[st].y<=aux.y)))
			st++;
		c[dr]=c[st];
	}
	c[st]=aux;
	return st;
}		

void qSort(int p,int q){
	int m=divide(p,q);
	if(m-1>p)
		qSort(p,m-1);
	if(m+1<q)
		qSort(m+1,q);
}

void initializareC2(){
	int i;
	n2=1;
	c2[1]=c[1];
	for(i=2;i<=n;i++){
		n2++;
		while(c[i].panta==c[i+1].panta){
			i++;
		}
		c2[n2]=c[i];
	}
}

double determinant(punct p1,punct p2,punct p3){
	return p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p3.x*p2.y-p2.x*p1.y-p1.x*p3.y;
}

void rezolvare(){
	detElemMin();
	detPante();
	qSort(2,n);
	initializareC2();
	int i;
	s[1]=c2[1];
	s[2]=c2[2];
	s[3]=c2[3];
	ns=3;
	for(i=4;i<=n2;i++){
		ns++;
		s[ns]=c2[i];
		while(determinant(s[ns-2],s[ns-1],s[ns])<0){
			s[ns-1]=s[ns];
			ns--;
		}
	}		
}

void afisare(){
	int i;
	printf("%d\n",ns);
	for(i=1;i<=ns;i++)
		printf("%lf %lf\n",s[i].x,s[i].y);
}

int main(){
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	citire();
	rezolvare();
	afisare();
	return 0;
}