Cod sursa(job #391074)

Utilizator johsonsbabiJohnsons Babi Minune johsonsbabi Data 4 februarie 2010 23:30:35
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define M1 120000
using namespace std;

FILE*f=fopen("cetati.in","r");
FILE*g=fopen("cetati.out","w");


double x[M1],y[M1];
int pi,n,i,a[M1],st[M1];

void citire(){
	fscanf(f,"%d",&n);
	pi=1;
	for(i=1;i<=n;i++){
		fscanf(f,"%lf %lf",&x[i],&y[i]);
		if(x[i]<x[pi] || (x[i]==x[pi] && y[i] <y[pi])){
			pi=i;
		}
	}
}

/*
	long double d1,d2;
	d1= (long double)(y[i]-y[pi])*(x[j]-x[pi]);
	d2=	(long double)(y[j]-y[pi])*(x[i]-x[pi]);
	return d1>d2;
*/
int cmp(int i,int j){
	long double d1,d2;
	d1= (long double)(y[i]-y[pi])*(x[j]-x[pi]);
	d2=	(long double)(y[j]-y[pi])*(x[i]-x[pi]);
	return d1>d2;
}

long double semn(int i1,int i2,int i3){
	return (long double) x[i1]*y[i2]+x[i2]*y[i3]+y[i1]*x[i3]-y[i2]*x[i3]-x[i1]*y[i3]-x[i2]*y[i1];
}

int main(){
	
	citire();
	for(i=1;i<=n;i++){
		if(i==pi) continue;
		a[++a[0]]=i;
	}
	//x[pi]+=(long double)1.1050003;
	//y[pi]+=(long double)1.1050003;
	sort(a+1,a+n,cmp);
	st[st[0]=1]=pi;
	for(i=1;i<n;i++){
		while(st[0]>=2 && semn( st[st[0]-1],st[st[0]],a[i]) > 0 )
			--st[0];
		st[++st[0]]=a[i];
	}
	fprintf(g,"%d\n",st[0]);
	reverse(st+1,st+st[0]);
	for(i=1;i<=st[0];i++){
		fprintf(g,"%lf %lf\n",x[st[i]],y[st[i]]);
	}
	fclose(f);
	fclose(g);
	return 0;
}