Cod sursa(job #121187)

Utilizator victorsbVictor Rusu victorsb Data 7 ianuarie 2008 22:36:35
Problema Camera Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define Nmax 2048
#define INF 0x3f3f3f3f
#define pd pair<double, double>
#define x first
#define y second
#define mp make_pair

const double eps = 1e-10;

int n, m;
pd p[Nmax];
pd d[Nmax];
pd tmp[Nmax];

void citire()
{
	int i;

	scanf("%d\n", &n);
	for (i = 1; i <= n; ++i)
		scanf("%lf %lf\n", &p[i].x, &p[i].y);
}

int semn(pd p0, pd p1, pd p2)
{
    p1.x -= p0.x, p1.y -= p0.y;
	p2.x -= p0.x, p2.y -= p0.y;

	double s = p2.x * p1.y - p1.x * p2.y;

	if (s > eps) return 1;
	if (s < -eps) return -1;
	return 0;
}

void coef(pd p1, pd p2, double &a, double &b, double &c)
{
	a = p2.y - p1.y;
	b = p1.x - p2.x;
	c = - (a * p1.x + b * p1.y);
}

pd intersec(pd p1, pd p2, pd q1, pd q2)
{
	double a1, b1, c1, a2, b2, c2;

	coef(p1, p2, a1, b1, c1);
	coef(q1, q2, a2, b2, c2);

	return mp((b1 * c2 - b2 * c1) / (a1 * b2 - a2 * b1) , (a1 * c2 - a2 * c1) / (a2 * b1 - a1 * b2));
}

double solve()
{
	int i, j, ct;
	double arie = 0;

	p[n + 1] = p[1];
	m = 0;
    d[++m] = mp(-INF, -INF);
	d[++m] = mp(INF, -INF);
	d[++m] = mp(INF, INF);
	d[++m] = mp(-INF, INF);

	for (i = 1; i <= n; ++i)
	{
		d[m + 1] = d[1];
		
		ct = 0;
		for (j = 1; j <= m; ++j)
		{
			if (semn(p[i], p[i + 1], d[j]) <= 0)
			   if (semn(p[i], p[i + 1], d[j + 1]) <= 0)
				   tmp[++ct] = d[j + 1];
			   else
				   tmp[++ct] = intersec(p[i], p[i + 1], d[j], d[j + 1]);
			else
				if (semn(p[i], p[i + 1], d[j + 1]) <= 0)
				{
					tmp[++ct] = intersec(p[i], p[i + 1], d[j], d[j + 1]);
					tmp[++ct] = d[j + 1];
				}
		}

		memcpy(d, tmp, sizeof(d));
		m = ct;
	}

	d[m + 1] = d[1];
	for (i = 1; i <= m; ++i)
		arie += d[i].x * d[i + 1].y - d[i + 1].x * d[i].y;
	arie /= 2;

	return arie;
}

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

	int i, t;
	double sol;

	//scanf("%d\n", &t);
	t = 1;
	for (i = 1; i <= t; ++i)
	{
		citire();

		sol = solve();
		reverse(p+1, p+n+1);
		sol = max(sol, solve());

		printf("%.2lf\n", sol);
	}

	return 0;
}