Cod sursa(job #600600)

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

struct punct {
	double x,y;
};

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

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

int main() {
	int i,nrmax,ve;
	punct smax;
	
	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];
	
	while(1) {
		ve=0;
		
		for(i=1;i<=n;++i) if(!ver[i]) {
			if(nr==1 && i==1)
				continue;
				
			if(ve==0 || (y[nr].y - x[i].y) * (y[nr].x - smax.x) > (y[nr].y - smax.y) * (y[nr].x - x[i].x)) {
				ve=1;
				smax=x[i]; nrmax=i;
			}
		}
		
		if(nrmax==1)
			break;
		
		y[++nr]=smax;
		ver[nrmax]=1;
	}
	
	printf("%d\n",nr);
	
	for(i=1;i<=nr;++i)
		printf("%.6lf %.6lf\n",y[i].x,y[i].y);
	
	return 0;
}