Cod sursa(job #461796)

Utilizator katakunaCazacu Alexandru katakuna Data 8 iunie 2010 17:10:20
Problema Camera Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define Nmax 4010
#define INF (100010)

struct punct {
	double x, y;
} P[Nmax], Q[Nmax], Nou[Nmax], A, B;

int Np, Nq, Nnou, Semn[Nmax];
double x, y;
double xmin = INF, xmax = -INF, ymin = INF, ymax = -INF;

int semn (double x1, double y1, double x2, double y2, double x3, double y3) {
	double A = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
	if (!A) return 0;
	if (A > 0) return 1;
	return -1;
}

double arie (double x1, double y1, double x2, double y2, double x3, double y3) {
	double A = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
	if (A < 0) A = -A;
	return A / 2;
}

void citire () {

    scanf ("%d", &Np);
    for (int i = 1; i <= Np; i++) {
        scanf ("%lf %lf", &P[i].x, &P[i].y);
        xmin = min (xmin, P[i].x); xmax = max (xmax, P[i].x);
        ymin = min (ymin, P[i].y); ymax = max (ymax, P[i].y);
    }
}


void coeficient (double x1, double y1, double x2, double y2, double &A, double &B, double &C) {
	A = y2 - y1;
	B = x1- x2;
	C = y1 * x2 - x1 * y2;
}

void intersect(punct A, punct B, punct C, punct D, double &x, double &y) {

	double A1, B1, C1, A2, B2, C2;
	coeficient (A.x, A.y, B.x, B.y, A1, B1, C1);
	coeficient (C.x, C.y, D.x, D.y, A2, B2, C2);

	if (A1 != 0) {
		y =  (C1 * A2 - A1 * C2) / (B2 * A1 - B1 * A2);
		x = - (B1 * y + C1) / A1;
	}
	else {
		y = - C1 / B1;
		x = - (B2 * y + C2) / A2;
	}

}

int egal (double a, double b) {
	a-= b;
	if (a < 0) a = -a;
	if (a < 0.00000000001) return 1;
	return 0;
}

double rezolva (int sgn) {
	
	Q[++Nq].x = xmin, Q[Nq].y = ymin; Q[++Nq].x = xmin, Q[Nq].y = ymax;
    Q[++Nq].x = xmax, Q[Nq].y = ymax; Q[++Nq].x = xmax, Q[Nq].y = ymin;
    Q[++Nq] = Q[1];

	int i, j, ok;
	double x, y;

	for (i = 2; i <= Np; i++) {
		
		Nnou = 0; ok = 0;
		for (j = 1; j <= Nq; j++)
			Semn[j] = semn (Q[j].x, Q[j]. y, P[i-1].x, P[i-1].y, P[i].x, P[i].y);
		
		for (j = 1; j < Nq; j++) {
			if (!Semn[j] && !Semn[j+1]) {
				ok = 10;
				break;
			}
			
			if (Semn[j] == sgn) {
				Nou[++Nnou].x = Q[j].x;
				Nou[Nnou].y = Q[j].y;
			}
			
			if (Semn[j] == 0) {
				Nou[++Nnou].x = Q[j].x;
				Nou[Nnou].y = Q[j].y;
			}
			
			if (Semn[j] && Semn[j + 1] && Semn[j] != Semn[j + 1]) {
				intersect (P[i-1], P[i], Q[j], Q[j + 1], x, y);
				Nou[++Nnou].x = x; Nou[Nnou].y = y;
			}
		}
		
		if (ok == 10) continue;
		
		Nou[++Nnou] = Nou[1];
		Nq = Nnou;
		for (j = 1; j <= Nnou; j++)
			Q[j] = Nou[j];
	}

	double Arie = 0;
	for (i = 3; i <= Nq; i++)
		Arie+= arie (Q[1].x, Q[1].y, Q[i-1].x, Q[i-1].y, Q[i].x, Q[i].y);

	return Arie;
}

int main () {

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

	citire ();
	printf ("%lf", max(rezolva (-1), rezolva (1)));

	return 0;
}