Cod sursa(job #331693)

Utilizator cotofanaCotofana Cristian cotofana Data 15 iulie 2009 01:05:47
Problema Camera Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#define dim 5000
#define inf 200000
#define x first
#define y second
#define eps 1e-6

using namespace std;

int n, nsol;
double s1, s2, xmin, xmax, ymin, ymax;
pair<double, double> a[dim], sol[dim];

double min(const double &x, const double &y) {
	return x<y?x:y;
}

double max(const double &x, const double &y) {
	return x<y?y:x;
}

double abs2(const double &x) {
	return x<0?-x:x;
}

bool equal(const double &x, const double &y) {
	return (abs(x-y)<=eps)?true:false;
}

int sign2(pair<double, double> a, pair<double, double> b, pair<double, double> c) {
	double q;
	q=a.x*(b.y-c.y)-a.y*(b.x-c.x)+b.x*c.y-b.y*c.x;
	if (abs2(q)<eps) return 0;
	if (q<0) return -1;
	return 1;
}

pair<double, double> intersect(pair<double, double> n1, pair<double, double> n2, pair<double, double> m1, pair<double, double> m2) {
	double a1, a2, b1, b2, c1, c2;
	
	a1=n1.y-n2.y;
	b1=n2.x-n1.x;
	c1=-(n2.y*n1.x-n2.x*n1.y);
	
	a2=m1.y-m2.y;
	b2=m2.x-m1.x;
	c2=-(m2.y*m1.x-m2.x*m1.y);
	
	pair<double, double> d;
	d.x=(c1*b2-b1*c2)/(a1*b2-b1*a2);
	d.y=(a1*c2-a2*c1)/(a1*b2-a2*b1);
	
	return d;
}

double calc(int sign) {
	int i, j, ncur;
	double s;
	pair<double, double> cur[dim];
	
	sol[1].x=xmin, sol[1].y=ymin;
	sol[2].x=xmax, sol[2].y=ymin;
	sol[3].x=xmax, sol[3].y=ymax;
	sol[4].x=xmin, sol[4].y=ymax;
	sol[5]=sol[1];
	nsol=4;
	
	for (i=1; i<=n; ++i) {
		int q, q1;
		
		for (j=1, ncur=0; j<=nsol; ++j) {
			q=sign2(sol[j], a[i], a[i+1]);
			q1=sign2(sol[j+1], a[i], a[i+1]);
			
			if (!q) cur[++ncur]=sol[j];
			else if (q==sign) {
				cur[++ncur]=sol[j];
				if (q1==-sign) cur[++ncur]=intersect(sol[j], sol[j+1], a[i], a[i+1]);
			}
			else if (q1==sign) cur[++ncur]=intersect(sol[j], sol[j+1], a[i], a[i+1]);
		}
		cur[++ncur]=cur[1];
		
		nsol=ncur;
		memcpy(sol, cur, sizeof(sol));
		
		if (!nsol) break;
	}
	
	s=0;
	
	for (i=1; i<=nsol; ++i)
		s+=sol[i].x*sol[i+1].y-sol[i].y*sol[i+1].x;
	s*=0.5;
	
	return abs2(s);
}

int main() {
	int i;
	freopen("camera.in", "r", stdin);
	freopen("camera.out", "w", stdout);
	
	xmin=ymin=inf;
	xmax=ymax=-inf;
	scanf("%d\n", &n);
	for (i=1; i<=n; ++i) {
		scanf("%lf %lf\n", &a[i].x, &a[i].y);
		xmin=min(xmin, a[i].x);
		xmax=max(xmax, a[i].x);
		ymin=min(ymin, a[i].y);
		ymax=max(ymax, a[i].y);
	}
	a[n+1]=a[1];
	
	s1=calc(1), s2=calc(-1);
	
	//printf("%.2lf\n", floor(100*max(s1, s2))/100);
	printf("%0.2lf\n", max(s1, s2));
	
	return 0;
}