Cod sursa(job #878291)

Utilizator dragosnicolaeNicolae Dragos dragosnicolae Data 14 februarie 2013 12:00:55
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>
#define er 0.0000000000001
#define nmax 120005
using namespace std;
double x[nmax],y[nmax];
int poz[nmax],n,s[nmax],vf;

double det(int i,int j,int k){
	return x[i]*y[j]+x[j]*y[k]+x[k]*y[i]-y[j]*x[k]-y[k]*x[i]-y[i]*x[j];
}
int cmp(int i,int j){
	return (y[i]-y[0])*(x[j]-x[0])<(x[i]-x[0])*(y[j]-y[0]);
}
void cit(){
	FILE *f;
	int i;
	f=fopen("infasuratoare.in","r");
	fscanf(f,"%d",&n);
	fscanf(f,"%lf%lf",&x[1],&y[1]);
	poz[0]=1;
	for(i=2;i<=n;i++){
		fscanf(f,"%lf%lf",&x[i],&y[i]);
		if(x[i]<x[poz[0]]||(fabs(x[i]-x[poz[0]])<=er&&y[i]<y[poz[0]]))
			poz[0]=i;
	}
	for(i=1;i<poz[0];i++)
		poz[i]=i;
	for(i=poz[0]+1;i<=n;i++)
		poz[i-1]=i;
	fclose(f);
}
int main(){
	cit();
	sort(poz+1,poz+n-1,cmp);
	vf=2;
	s[1]=poz[0];
	s[2]=poz[1];
	for(int i=2;i<n;i++){
		while(vf>=2&&det(s[vf-1],s[vf],poz[i])<=0)
			vf--;
		vf++;
		s[vf]=poz[i];
	}
	FILE *f;
	f=fopen("infasuratoare.out","w");
	fprintf(f,"%d\n",vf);
	for(int i=1;i<=vf;i++)
		fprintf(f,"%lf %lf\n",x[s[i]],y[s[i]]);
	fclose(f);
	return 0;
}