Cod sursa(job #727783)

Utilizator dragosnicolaeNicolae Dragos dragosnicolae Data 28 martie 2012 11:53:24
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<stdio.h>
#include<algorithm>
#define nmax 120005
using namespace std;
int n,poz[nmax],s[nmax],vf;
double x[nmax],y[nmax];
//||((y[i]-y[0])*(x[j]-x[0])>(y[j]-y[0])*(x[i]-x[0])&&dist(0,i)<dist(0,j))
int cmp(int i,int j){
	return (y[i]-y[0])*(x[j]-x[0])<(y[j]-y[0])*(x[i]-x[0]);
}
double det(int i,int j,int k){
	return x[i]*y[j]+x[j]*y[k]+x[k]*y[i]-x[k]*y[j]-x[j]*y[i]-x[i]*y[k];
}
void cit(){
	FILE *f;
	int i;
	f=fopen("infasuratoare.in","r");
	fscanf(f,"%d",&n);
	x[0]=y[0]=(double)2000000000;
	for(i=1;i<=n;i++){
		fscanf(f,"%lf%lf",&x[i],&y[i]);
		if(x[i]<x[0]||(x[i]==x[0]&&y[i]<y[0])){
			x[0]=x[i];
			y[0]=y[i];
			poz[0]=i;
		}
	}
	for(i=1;i<poz[0];i++)
		poz[i]=i;
	for(i=poz[0]+1;i<=n;i++){
		x[i-1]=x[i];
		y[i-1]=y[i];
		poz[i-1]=i-1;
	}
	poz[0]=0;
	fclose(f);
}
void afis(){
	int i;
	FILE *f;
	f=fopen("infasuratoare.out","w");
	fprintf(f,"%d\n",vf);
	for(i=1;i<=vf;i++)
		fprintf(f,"%lf %lf\n",x[s[i]],y[s[i]]);
	fclose(f);
}
int main(){
	cit();
	sort(poz+1,poz+n,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];
	}
	afis();
	return 0;
}