Cod sursa(job #878316)

Utilizator dragosnicolaeNicolae Dragos dragosnicolae Data 14 februarie 2013 12:19:53
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 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[poz[0]])*(x[j]-x[poz[0]])<(x[i]-x[poz[0]])*(y[j]-y[poz[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]]||(x[i]==x[poz[0]]&&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,cmp);
	for(int i=0;i<n;i++)
		printf("%lf %lf\n",x[poz[i]],y[poz[i]]);
	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;
}