Cod sursa(job #544808)

Utilizator Robert29FMI Tilica Robert Robert29 Data 2 martie 2011 10:18:36
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE*f=fopen("infasuratoare.in","r");
FILE*g=fopen("infasuratoare.out","w");
int n,minx,miny,pozi,j,i,poz;
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[
	
	fclose(g);
	fclose(f);
	return 0;
}