Cod sursa(job #946944)

Utilizator deividFlorentin Dumitru deivid Data 6 mai 2013 13:23:01
Problema Rubarba Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.99 kb
#include<stdio.h>
#include<algorithm>
#include<cmath>

#define maxn 100005
#define calipers 5
#define inf_LL (1LL<<61)

using namespace std;

FILE*f=fopen("rubarba.in","r");
FILE*g=fopen("rubarba.out","w");

int n;
int st[maxn],used[maxn],Next[maxn],prec[maxn],ind[calipers];
double unghi[calipers],Next_angle[maxn];
const double pi = 3.141592653589793238462643;

struct point{
	int x,y;
}A[maxn],aux[maxn];

struct cmp{
	inline bool operator () ( const point &a , const point &b ){
		if ( a.x != b.x )	return a.x < b.x;
		return a.y < b.y;
	}
};

inline long long det ( const point &a , const point &b , const point &c ){
	
	long long d = 1LL*(b.x-a.x)*(c.y-a.y) - 1LL*(c.x-a.x)*(b.y-a.y);
	return d;
}

inline int infasuratoare ( point *A , int n ){
	
	sort(A+1,A+n+1,cmp());
	int new_n = 0;
	for ( int i = 1 ; i <= n ; ++i ){
		if ( A[i].x != A[i-1].x || A[i].y != A[i-1].y || i == 1 ){
			A[++new_n] = A[i];
		}
	}
	n = new_n;
	
	if ( n == 2 ){
		return 2;
	}
	
	int vf = 0;
	st[++vf] = 1,st[++vf] = 2; used[2] = 1;
	for ( int i = 3 ; i <= n ; ++i ){
		
		while ( vf >= 2 && det(A[st[vf-1]],A[st[vf]],A[i]) <= 0 ){
			used[st[vf--]] = 0;
		}
		st[++vf] = i;
		used[i] = 1;
	}
	
	for ( int i = n ; i >= 1 ; --i ){
		if ( A[i].x == A[n].x || used[i] )	continue ;
		
		while ( vf >= 2 && det(A[st[vf-1]],A[st[vf]],A[i]) <= 0 ){
			used[st[vf--]] = 0;
		}
		st[++vf] = i;
		used[i] = 1;
	}
	
	n = vf-1;
	for ( int i = 1 ; i < vf ; ++i ){
		aux[i] = A[st[i]];
	}
	for ( int i = 1 ; i < vf ; ++i ){
		A[i] = aux[i];
	}
	
	return n;
}

double grade ( double unghi ){
	return 180*unghi/pi;
}

inline void get_angles () {
	
	for ( int i = 1 ; i <= n ; ++i ){
		Next[i] = i+1;
		prec[i] = i-1;
	}
	Next[n] = 1; prec[1] = n;
	
	
	for ( int i = 1 ; i <= n ; ++i ){
		point a = A[i],o = A[Next[i]],b = A[Next[Next[i]]];
		
		double angle1 = atan2(a.y-o.y,a.x-o.x);
		if ( angle1 < 0 )	angle1 += 2*pi;
		double angle2 = atan2(b.y-o.y,b.x-o.x);
		if ( angle2 < 0 )	angle2 += 2*pi;
		
		if ( angle1 < angle2 ){
			Next_angle[i] = angle2-angle1-pi;
		}
		else{
			Next_angle[i] = pi-(angle1-angle2);
		}
	}
}

inline void get_start () {
	
	for ( int i = 1 ; i < calipers ; ++i )	ind[i] = 1;
	for ( int i = 2 ; i <= n ; ++i ){
		
		if ( A[i].x < A[ind[1]].x || (A[i].x == A[ind[1]].x && A[i].y < A[ind[1]].y) )	ind[1] = i;
		if ( A[i].x > A[ind[2]].x || (A[i].x == A[ind[2]].x && A[i].y > A[ind[2]].y) )	ind[2] = i;
		if ( A[i].y < A[ind[3]].y || (A[i].y == A[ind[3]].y && A[i].x < A[ind[3]].x) )	ind[3] = i;
		if ( A[i].y > A[ind[4]].y || (A[i].y == A[ind[4]].y && A[i].x > A[ind[4]].x) )	ind[4] = i;
	}
	
	int p;
	
	p = ind[1];
	unghi[1] = atan2(A[Next[p]].y-A[p].y,A[Next[p]].x-A[p].x);
	if ( unghi[1] < 0 )	unghi[1] += 2*pi;
	unghi[1] -= 3*pi/2;
	if ( unghi[1] < 0 )	unghi[1] += 2*pi;
	
	p = ind[2];
	unghi[2] = atan2(A[Next[p]].y-A[p].y,A[Next[p]].x-A[p].x);
	if ( unghi[2] < 0 )	unghi[2] += 2*pi;
	unghi[2] -= pi/2;
	
	p = ind[3];
	unghi[3] = atan2(A[Next[p]].y-A[p].y,A[Next[p]].x-A[p].x);
	
	p = ind[4];
	unghi[4] = atan2(A[Next[p]].y-A[p].y,A[Next[p]].x-A[p].x);
	if ( unghi[4] < 0 )	unghi[4] += 2*pi;
	unghi[4] -= pi;
}

inline double modul ( const double &j ){
	if ( j < 0 )	return -j;
	return j;
}

inline double dist ( double x1 , double y1 , double x2 , double y2 ){
	
	double d = (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
	return sqrt(d);
}

inline double get_area ( int x , int y , int z , int t ){
	
	long long a,b,c;
	a = A[prec[x]].y-A[x].y,b = A[x].x-A[prec[x]].x,c = -1LL*A[x].x*(A[prec[x]].y-A[x].y) + 1LL*A[x].y*(A[prec[x]].x-A[x].x);
	double num = sqrt(a*a+b*b);
	
	double l = modul(a*A[y].x+b*A[y].y+c) / num,h;
	
	if ( !a ){
		h = modul((double)(A[t].x-A[z].x));
	}
	else{
		if ( !b ){
			h = modul((double)(A[t].y-A[z].y));
		}
		else{
			double m = 1/((double)a/b);
			double aprim = m,bprim = -1,cprim = -m*(A[z].x)+A[z].y;
			double xint1 = (c*bprim - b*cprim)/(aprim*b - a*bprim);
			double yint1 = (-c-a*xint1)/b;
			
			aprim = m,bprim = -1,cprim = -m*(A[t].x)+A[t].y;
			double xint2 = (c*bprim - b*cprim)/(aprim*b - a*bprim);
			double yint2 = (-c-a*xint2)/b;
			h = dist(xint1,yint1,xint2,yint2);
		}
	}
	
	return l*h;
}

int main () {
	
	fscanf(f,"%d",&n);
	for ( int i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d %d",&A[i].x,&A[i].y);
	}
	
	n = infasuratoare(A,n);
	
	get_angles();
	
	get_start();
	
	int start1 = ind[1],primul = 1; double sol = inf_LL;
	for ( ; ind[1] != start1 || primul ; ){
		
		int p = calipers-1;
		for ( int i = calipers-2 ; i >= 1 ; --i ){ 
			if ( unghi[i] < unghi[p] ){
				p = i;
			}
		}
		for ( int i = 1 ; i < calipers ; ++i ){
			
			if ( i != p ){
				unghi[i] -= unghi[p];
			}
		}
		unghi[p] = Next_angle[ind[p]];
		ind[p] = Next[ind[p]];
		
		if ( p == 1 )	sol = min(sol,get_area(ind[1],ind[2],ind[3],ind[4]));
		if ( p == 2 )	sol = min(sol,get_area(ind[2],ind[1],ind[3],ind[4]));
		if ( p == 3 )	sol = min(sol,get_area(ind[3],ind[4],ind[1],ind[2]));
		if ( p == 4 )	sol = min(sol,get_area(ind[4],ind[3],ind[1],ind[2]));
		
		if ( p == 1 ){
			primul = 0;
		}
	}
	
	if ( sol == inf_LL )	sol = 0;
	fprintf(g,"%.2lf\n",sol);
	
	fclose(f);
	fclose(g);
	
	return 0;
}