Cod sursa(job #349811)

Utilizator savimSerban Andrei Stan savim Data 21 septembrie 2009 16:34:59
Problema Camera Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
#include <stdio.h>

#define MAX_N 10010
#define inf 200000

int n, m, k, poz;
int use[MAX_N];
struct segment {
	double x1, y1, x2, y2;
} v[MAX_N], p[MAX_N], q[MAX_N];
double sol, x, y, mp, mq, np, nq, a, b;

void cit() {
	freopen("camera.in", "r", stdin);
	freopen("camera.out", "w", stdout);

    scanf("%d", &n);

	scanf("%lf %lf", &v[1].x1, &v[1].y1);

	for (int i = 1; i < n; i++) {
    	scanf("%lf %lf", &v[i].x2, &v[i].y2);
		v[i + 1].x1 = v[i].x2; v[i + 1].y1 = v[i].y2;
	}
	v[n].x2 = v[1].x1; v[n].y2 = v[1].y1;
}

void init() {
	m = 4;
	p[1].x1 = -inf; p[1].y1 = -inf; p[1].x2 = inf; p[1].y2 = -inf;
	p[2].x1 = inf; p[2].y1 = -inf; p[2].x2 = inf; p[2].y2 = inf;
	p[3].x1 = inf; p[3].y1 = inf; p[3].x2 = -inf; p[3].y2 = inf;
	p[4].x1 = -inf; p[4].y1 = inf; p[4].x2 = -inf; p[4].y2 = -inf;

	use[1] = use[2] = use[3] = use[4] = 1;
}

inline double det(double x1, double y1, double x2, double y2, double x3, double y3) {
	return (double) x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2;
}

inline double tangenta(segment A) {
	if (A.x1 != A.x2) return 1.0 * (A.y2 - A.y1) / (A.x2 - A.x1);
	else return inf;
}

void intersect(segment P, segment Q) {
	mp = tangenta(P);
	np = P.y1 - mp * P.x1;

	mq = tangenta(Q);
	nq = Q.y1 - mq * Q.x1;

	if (mp == inf) {
		x = P.x1;
		y = mq * x + nq;
	}
	else if (mq == inf) {
			x = Q.x1;
			y = mp * x + np;
		 }
		 else {
			if (1.0 * (P.y2 - P.y1) * (Q.x2 - Q.x1) == 0 && 1.0 * (Q.y2 - Q.y1) * (P.x2 - P.x1) == 0) for(;;);
         	x = 1.0 * (np - nq) / (mq - mp);
			y = mp * x + np;
		 }
}

inline int verif(int t, int r) {
	if (q[t].x2 != p[r].x1 || q[t].y2 != p[r].y1) return 1;
	return 0;
}

void add(int t, int r) {
	q[k + 1].x1 = q[k].x2; q[k + 1].y1 = q[k].y2;
    q[k + 1].x2 = p[r].x1; q[k + 1].y2 = p[r].y1;
	use[++k] = 1;
}

void solve(int semn) {
	init();
	
	for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= m; j++) {
			a = 1.0 * det(v[i].x1, v[i].y1, v[i].x2, v[i].y2, p[j].x1, p[j].y1) * semn;
			b = 1.0 * det(v[i].x1, v[i].y1, v[i].x2, v[i].y2, p[j].x2, p[j].y2) * semn;

			if (a <= 0 && b <= 0) use[j] = 0;
			else if ((a < 0 && b > 0) || (b < 0 && a > 0)) {
					intersect(p[j], v[i]);

					if (a < 0) {
						p[j].x1 = x;
						p[j].y1 = y;
					}
					else {
                    	p[j].x2 = x;
						p[j].y2 = y;
					}
				 }
		}
	    
		k = 0; poz = 0;
		for (int j = 1; j <= m; j++)
			if (use[j]) {
				if (!poz) poz = j;
            	if (k && verif(k, j))
					add(k, j);
				q[++k] = p[j];
				use[k] = 1;
			}
				
		if (verif(k, poz))
			add(k, poz);
		m = k;
		for (int j = 1; j <= m; j++) p[j] = q[j];
	}

	double sup = 0;
   	for (int i = 1; i <= m; i++)
		sup = sup + p[i].x1 * p[i].y2 - p[i].x2 * p[i].y1;
	sup = 1.0 * sup / 2;
	if (sup < 0) sup = 0;

	if (sup > sol) sol = sup;
}

int main() {

	cit();
	solve(-1);
	if (!sol) solve(1);
	
	printf("%.2lf\n", sol);

	return 0;
}