Cod sursa(job #709550)

Utilizator halianStefanca Stefan halian Data 8 martie 2012 11:23:20
Problema Rubarba Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.51 kb
#include <stdio.h>
#include <math.h>
#define FI fopen("rubarba.in","r")
#define FO fopen("rubarba.out","w")

template <class T> T abs(T a) { if(a<0) return -a; return a; }
struct Punct {
	long x,y;
	double dist(Punct p) {
		return sqrt((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y));
	}
} stiva[100001],punct[100000];
struct Dreapta {
	double a,b,c;
	double dist(Punct p) {
		return abs(a*p.x + b*p.y + c)/sqrt(a*a+b*b);
	}
};
long n,stivaSize;
double sol;

void citeste (FILE *f) {
	long i;
	fscanf(f,"%li",&n);
	for(i=0;i<n;i++)
		fscanf(f,"%li%li",&punct[i].x,&punct[i].y);
}

int compara(Punct a,Punct b) {
	if(a.x<b.x)
		return 1;
	if(a.x>b.x)
		return 0;
	if(a.y<b.y)
		return 1;
	return 0;
}

void schimba(Punct &a, Punct &b) {
	Punct aux=a;a=b;b=aux; 
}

void sort(long li,long ls) {
	long i,j;
	if(li>=ls) return;
	for(i=j=li+1;i<=ls;i++)
		if(compara(punct[i],punct[li]))
			schimba(punct[i],punct[j++]);
	schimba(punct[li],punct[j-1]);
	sort(li,j-2);
	sort(j,ls);
}

long produs(Punct a,Punct b,Punct c) {
	return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
}

void infasuratoare() {
	int i;
	stiva[0]=punct[0];
	stiva[1]=punct[1];
	stivaSize=2;
	for(i=2;i<n;i++)
		if(produs(stiva[stivaSize-2],stiva[stivaSize-1],punct[i])>=0) {
			stiva[stivaSize]=punct[i];
			stivaSize++;
		}
		else {
			stiva[stivaSize-1]=punct[i];
			while(stivaSize>2 && produs(stiva[stivaSize-3],stiva[stivaSize-2],stiva[stivaSize-1])<0) {
				stivaSize--;
				stiva[stivaSize-1]=stiva[stivaSize];
			}
		}
	for(i=n-2;i>=0;i--)
		if(produs(stiva[stivaSize-2],stiva[stivaSize-1],punct[i])>=0) {
			stiva[stivaSize]=punct[i];
			stivaSize++;
		}
		else {
			stiva[stivaSize-1]=punct[i];
			while(stivaSize>2 && produs(stiva[stivaSize-3],stiva[stivaSize-2],stiva[stivaSize-1])<0) {
				stivaSize--;
				stiva[stivaSize-1]=stiva[stivaSize];
			}
		}
	stivaSize--;
}

long stivaVal(long val) {
	return val%stivaSize;
}

int stivaValCmp(long a,long b) {
	if(a!=b+1)
		return 1;
	return 0;
}

void rez() {
	long i,j,st,dr;
	double jDist,stDist,drDist,aux,k,arie,x,y;
	i=j=0;
	dr=1;
	st=-1;
	Dreapta d1,d2;
	for(;i<stivaSize;i++) {
		d1.a=stiva[stivaVal(i)].y-stiva[stivaVal(i+1)].y;
		d1.b=stiva[stivaVal(i+1)].x-stiva[stivaVal(i)].x;
		d1.c=stiva[stivaVal(i)].x*stiva[stivaVal(i+1)].y - stiva[stivaVal(i)].y*stiva[stivaVal(i+1)].x;
		jDist=d1.dist(stiva[stivaVal(j)]);
		aux=d1.dist(stiva[stivaVal(j+1)]);
		for(;jDist<=aux;j++) {
			jDist=aux;
			aux=d1.dist(stiva[stivaVal(j+2)]);
		}
		//k=(double)(stiva[stivaVal(j)].dist(stiva[stivaVal(i)]))/stiva[stivaVal(j)].dist(stiva[stivaVal(i+1)]);
		//x=(1/(1+k))*stiva[stivaVal(i)].x+(k/(1+k))*stiva[stivaVal(i+1)].x;
		//y=(1/(1+k))*stiva[stivaVal(i)].y+(k/(1+k))*stiva[stivaVal(i+1)].y;
		d2.a=-d1.b;
		d2.b=d1.a;
		d2.c=-d2.a*stiva[stivaVal(j)].x-d2.b*stiva[stivaVal(j)].y;
		drDist=d2.dist(stiva[stivaVal(dr)]);
		aux=d2.dist(stiva[stivaVal(dr+1)]);
		for(;drDist<=aux && stivaValCmp(dr,j);dr++) {
			drDist=aux;
			aux=d2.dist(stiva[stivaVal(dr+2)]);
		}
		if(st==-1)
			st=j+1;
		stDist=d2.dist(stiva[stivaVal(st)]);
		aux=d2.dist(stiva[stivaVal(st+1)]);
		for(;stDist<=aux && stivaValCmp(st,i);st++) {
			stDist=aux;
			aux=d2.dist(stiva[stivaVal(st+2)]);
		}
		arie=jDist*(stDist+drDist);
		if(arie<sol)
			sol=arie;
	}
}

int main() {
	citeste(FI);
	if(n<=2) {
		fprintf(FO,"0.00");
		return 0;
	}
	sort(0,n-1);
	infasuratoare();
	sol=1000000;
	sol*=sol;
	sol*=sqrt(2);
	rez();
	fprintf(FO,"%.2lf",sol);
	return 0;
}