Cod sursa(job #616245)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 11 octombrie 2011 23:24:57
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <algorithm>

using namespace std;


const int N=120001;

struct punct{
	double x,y;
}x[N],y[N],z[N];
	
bool comp(punct a,punct b){
	return a.x<b.x;
}

int n,nr1,nr2;

int main(){
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++){
		scanf("%lf%lf",&x[i].x,&x[i].y);
	}
	sort(&x[1],&x[n+1],comp);
	y[++nr1]=x[1];
	for(i=2;i<=n;i++){
		while(nr1>1 && (x[i].y - y[nr1].y) * (x[i].x - y[nr1-1].x) <= (x[i].x - y[nr1].x) * (x[i].y - y[nr1-1].y))
			--nr1;
		y[++nr1]=x[i];
	}
	z[++nr2]=x[1];
	for(i=2;i<=n;++i){		
		while(nr2>1 && (x[i].y - z[nr2].y) * (x[i].x - z[nr2-1].x) >= (x[i].x - z[nr2].x) * (x[i].y - z[nr2-1].y))
			--nr2;
		z[++nr2]=x[i];
	}
	printf("%d\n",nr1+nr2-2);
	for(i=1;i<=nr1;++i)
		printf("%.6lf %.6lf\n",y[i].x,y[i].y);
	for(i=nr2-1;i>1;--i)
		printf("%.6lf %.6lf\n",z[i].x,z[i].y);
	return 0;
}