Cod sursa(job #720883)

Utilizator valiro21Valentin Rosca valiro21 Data 22 martie 2012 23:46:12
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstdio>
#include <algorithm>
#define NMax 120021

using namespace std;

struct point{
	double x,y;} ve[NMax];

int n,q[NMax];

bool cmp(point a,point b){
	return (a.x - ve[1].x) * (b.y - ve[1].y) > (b.x - ve[1].x) * (a.y - ve[1].y);}

double left_turn(int i1, int i2, int i3) {
	return ve[i1].x * ve[i2].y + ve[i2].x * ve[i3].y + ve[i3].x * ve[i1].y - ve[i1].y * ve[i2].x - ve[i2].y * ve[i3].x - ve[i3].y * ve[i1].x;}

int main(){
	freopen("infasuratoare.in","rt",stdin);
	freopen("infasuratoare.out","wt",stdout);
	
	scanf("%ld",&n);

	for(long i=1;i<=n;i++){
		scanf("%lf %lf",&ve[i].x,&ve[i].y);
		if(ve[i].y < ve[1].y || (ve[i].y == ve[1].y && ve[i].x<ve[1].x) ){
			point aux=ve[1];ve[1]=ve[i];ve[i]=aux;}
	}

	sort(ve+2,ve+n+1,cmp);

	q[++q[0]]=1;
	for(long i=2;i<=n;i++){
		while (q[0] >= 2 && ( left_turn( q[q[0]-1], q[q[0]], i) < 0 ) )
			q[0]--;
		q[++q[0]]=i;
	}

	printf("%ld\n",q[0]);
	for(long i=1;i<=q[0];i++)
		printf("%lf %lf\n",ve[q[i]].x,ve[q[i]].y);

	return 0;
}