Cod sursa(job #347362)

Utilizator CezarMocanCezar Mocan CezarMocan Data 11 septembrie 2009 21:47:38
Problema Camera Scor 70
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.31 kb
#include <cstdio>
#include <cstring>
#include <math.h>
#define maxc 100100
#define maxn 2027
#define eps 0.00000001

using namespace std;

struct punct {
	double x, y;
};

int i, j, n, nr, nrnou;
punct p[maxn];
punct v[maxn], vnou[maxn];
double sol;

inline double max(double a, double b) {
	if (a > b)
		return a;
	return b;
}

inline int smn(double a, double b, double c, punct z) {
	double t = a * z.x + b * z.y + c;
	if (t + eps < 0)
		return -1;
	if (t - eps > 0)
		return 1;
	return 0;
}

inline void intersect(double a1, double b1, double c1, double a2, double b2, double c2, punct &p) {
	p.y = (c1 * a2 / a1 - c2) / (-b1 * a2 / a1 + b2);
	p.x = (-b1*p.y - c1) / a1;
}

inline double solve(int semn) {
	bool ok; //ok o sa imi tina daca la momentu curent sunt in sau inafara poligonului
	int i;
	double a1, b1, c1, a2, b2, c2, area;
	punct pt;
	
	memset(v, 0, sizeof(v));
	nr = 4;
	v[1].x = -maxc; v[1].y = -maxc;
	v[2].x = -maxc; v[2].y = maxc;
	v[3].x = maxc; v[3].y = maxc;
	v[4].x = maxc; v[4].y = -maxc;
	v[nr + 1] = v[1];
	
	nrnou = 0;
	
	for (i = 1; i <= n; i++) {
		a1 = p[i].y - p[i + 1].y;
		b1 = p[i + 1].x - p[i].x;
		c1 = p[i].x * p[i + 1].y - p[i + 1].x * p[i].y;
		
		if (smn(a1, b1, c1, v[1]) == semn)
			ok = 1;
		else
			ok = 0;
		
		nrnou = 0;
		for (j = 1; j <= nr; j++) {
			a2 = v[j].y - v[j + 1].y;
			b2 = v[j + 1].x - v[j].x;
			c2 = v[j].x * v[j + 1].y - v[j + 1].x * v[j].y;
			
			if (smn(a1, b1, c1, v[j]) == smn(a1, b1, c1, v[j + 1])) 
				if (ok == 1) {
					nrnou++;
					vnou[nrnou] = v[j];
				}
				else;
			else {
				intersect(a1, b1, c1, a2, b2, c2, pt);
				if (ok == 0) {
					nrnou++;
					vnou[nrnou] = pt;
					ok = 1;
				}
				else {
					nrnou++;
					vnou[nrnou] = v[j];
					nrnou++;
					vnou[nrnou] = pt;
					ok = 0;
				}
			}
		}
		nr = nrnou;
		memcpy(v, vnou, sizeof(v));
		v[nr + 1] = v[1];
	}
	
	area = 0;
	for (i = 1; i <= nr; i++)
		area += (v[i].x * v[i + 1].y - v[i + 1].x * v[i].y);
	
	return fabs(area / 2.0);
}

int main() {
	freopen("camera.in", "r", stdin);
	freopen("camera.out", "w", stdout);
	
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
		scanf("%lf%lf", &p[i].x, &p[i].y);
	p[n + 1] = p[1];
	
	sol = max(solve(1), solve(-1));
	
	printf("%.2lf\n", sol);
	
	return 0;
}