Cod sursa(job #544817)

Utilizator Robert29FMI Tilica Robert Robert29 Data 2 martie 2011 10:38:36
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE*f=fopen("infasuratoare.in","r");
FILE*g=fopen("infasuratoare.out","w");
double minx,miny;
int n,j,i,poz,stv[120001],k;
struct punct{
	double x;
	double y;
	double ctg;
} v[120001];
int cmp(punct a,punct b){
	return a.ctg>b.ctg;
}
int ver(int i1,int i2,int i3){
	if(v[i2].x*v[i3].y+v[i1].x*v[i2].y+v[i3].x*v[i1].y>v[i2].x*v[i1].y+v[i1].x*v[i3].y+v[i3].x*v[i2].y)
		return 1;
	else
		return 0;
}
int main() {
	fscanf(f,"%d",&n);
	miny=1000000000;
	for(i=1;i<=n;++i){
		fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
		if(miny>v[i].y){
			miny=v[i].y;
			minx=v[i].x;
			poz=i;
		}
	}
	
	for(i=1;i<=n;++i){
		v[i].x-=minx;
		v[i].y-=miny;
		v[i].ctg=v[i].x/v[i].y;
	}
	v[poz].x=v[1].x;
	v[poz].y=v[1].y;
	v[1].x=v[1].y=0;
	v[0].ctg=0;
	
	sort(v+2,v+n+1,cmp);
	
	stv[1]=1;
	stv[2]=2;
	k=2;
	
	for(i=3;i<=n;++i){
		while(!ver(stv[k-1],stv[k],i)){
			k--;
		}
		stv[++k]=i;
	}
	
	fprintf(g,"%d\n",k);
	
	for(i=1;i<=k;++i)
		fprintf(g,"%lf %lf\n",v[stv[i]].x+minx,v[stv[i]].y+miny);
	fclose(g);
	fclose(f);
	return 0;
}