Cod sursa(job #121625)

Utilizator gcosminGheorghe Cosmin gcosmin Data 9 ianuarie 2008 09:46:22
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.64 kb
#include <stdio.h>
#include <vector>
using namespace std;

#define NMAX 4010
#define eps 1e-6
#define INF 200000
#define doubl double
#define punct pair <doubl, doubl>
#define x first
#define y second

inline doubl DABS(doubl x) { return (x < 0) ? -x : x; }
inline doubl DMIN(doubl a, doubl b) { return (a < b) ? a : b; }
inline doubl DMAX(doubl a, doubl b) { return (a > b) ? a : b; }
inline int egal(doubl a, doubl b) { return DABS(a - b) <= eps; }

int N;

doubl xmin, xmax, ymin, ymax;

punct A[NMAX];

int nrez;
punct rez[NMAX];
int ncur;
punct cur[NMAX];

int semn(punct a, punct b, punct c)
{
	doubl q = a.first * (b.second - c.second) - a.second * (b.first - c.first) + b.first * c.second - b.second * c.first;
	if (DABS(q) < eps) return 0;
	if (q < 0) return -1;
return 1;
}

int nr_inter_oriz(punct a, punct b, int lat)
{
	int nr = 0, i;

	for (i = 0; i < N; i++)
	{
		if (i == lat) continue;
		if (egal(a.second, A[i].second) || egal(a.second, A[i+1].second)) 
		{
			if (egal(A[i].second, A[i+1].second)) continue;
			nr += egal(a.second, DMIN(A[i].second, A[i+1].second));
			continue;
		}
		nr += semn(A[i], a, b) * semn(A[i+1], a, b) < 0 && semn(a, A[i], A[i+1]) * semn(b, A[i], A[i+1]) < 0;
	}

return nr;		
}
int nr_inter_vert(punct a, punct b, int lat)
{
	int nr = 0, i;

	for (i = 0; i < N; i++)
	{
		if (i == lat) continue;
		if (egal(a.first, A[i].first) || egal(a.first, A[i+1].first))
		{
			if (egal(A[i].first, A[i+1].first)) continue;
			nr += egal(a.first, DMIN(A[i].first, A[i+1].first));
			continue;
		}
		nr += semn(A[i], a, b) * semn(A[i+1], a, b) < 0 && semn(a, A[i], A[i+1]) * semn(b, A[i], A[i+1]) < 0;
	}
return nr;
}

punct inter(punct A, punct B, punct C, punct D)
{
	doubl a1, b1, c1, a2, b2, c2;

	a1 = A.second - B.second;
	b1 = B.first - A.first;
	c1 = - (A.first * B.second - A.second * B.first);

	a2 = C.second - D.second;
	b2 = D.first - C.first;
	c2 = - (C.first * D.second - C.second * D.first);

	punct aux;
	aux.first = (c1 * b2 - b1 * c2) / (a1 * b2 - b1 * a2);
	aux.second = (a1 * c2 - c1 * a2) / (a1 * b2 - b1 * a2);

return aux;
}

double calc(int smn)
{
	int i, j;
	
	nrez = 4;
	rez[0].first = xmin; rez[0].second = ymin;
	rez[1].first = xmax; rez[1].second = ymin;
	rez[2].first = xmax; rez[2].second = ymax;
	rez[3].first = xmin; rez[3].second = ymax;
	rez[4] = rez[0];

	punct mij, aux;
	doubl w;
	for (i = 0; i < N; i++)
	{
		int q, q1;
		for (j = 0, ncur = 0; j < nrez; j++)
		{
			q = semn(rez[j], A[i], A[i+1]);
			q1 = semn(rez[j+1], A[i], A[i+1]);

			if (!q) cur[ncur++] = rez[j];
			else
			{
				if (q == smn) 
				{
					cur[ncur++] = rez[j];
					if (q1 == -smn) cur[ncur++] = inter(rez[j], rez[j+1], A[i], A[i+1]);
				}
				else
				{
					if (q1 == smn) cur[ncur++] = inter(rez[j], rez[j+1], A[i], A[i+1]);
				}
			}
		}
		cur[ncur] = cur[0];

		nrez = ncur;
		memcpy(rez, cur, sizeof(rez));
		
		if (!nrez) break;
	}

	doubl ar = 0;

	for (i = 0; i < ncur; i++)
		ar += rez[i].first * rez[i+1].second - rez[i].second * rez[i+1].first;
	ar *= 0.5;
	return DABS(ar);
}

int main()
{
	int i;
	xmin = INF, xmax = -INF, ymin = INF, ymax = -INF;
	
	freopen("camera.in", "r", stdin);
	freopen("camera.out", "w", stdout);

	scanf("%d", &N);

	for (i = 0; i < N; i++)
	{
		scanf("%lf %lf", &A[i].first, &A[i].second);
		xmin = DMIN(xmin, A[i].first);
		xmax = DMAX(xmax, A[i].first);
		ymin = DMIN(ymin, A[i].second);
		ymax = DMAX(ymax, A[i].second);		
	}
	A[i] = A[0];
	
	doubl ar1 = calc(1), ar2 = calc(-1);
	
	printf("%0.2lf\n", DMAX(ar1, ar2));
	
fclose(stdin);
fclose(stdout);
return 0;
}