Cod sursa(job #600609)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 2 iulie 2011 16:39:21
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<stdio.h>
#include<algorithm>
#define N 120001
using namespace std;

struct punct {
	double x,y;
};

int n,nr,nr2;
punct x[N],y[N],z[N];
bool ver[N];

bool cmp(punct a,punct b) {
	return a.x<b.x;
}

int main() {
	int i;
	
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	
	scanf("%d",&n);
	
	for(i=1;i<=n;++i)
		scanf("%lf%lf",&x[i].x,&x[i].y);
	
	sort(&x[1],&x[n+1],cmp);
	
	y[++nr]=x[1];
	
	for(i=2;i<=n;++i) {
		
		while(nr>1 && (x[i].y - y[nr].y) * (x[i].x - y[nr-1].x) <= (x[i].x - y[nr].x) * (x[i].y - y[nr-1].y))
			--nr;
		
		y[++nr]=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",nr+nr2-2);
	
	for(i=1;i<=nr;++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;
}