Cod sursa(job #1964)

Utilizator gcosminGheorghe Cosmin gcosmin Data 15 decembrie 2006 15:23:55
Problema Camera Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.8 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>

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;

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;
}

int main()
{
	int i;
	doubl 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];

	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;
	int smn, j;
	for (i = 0; i < N; i++)
	{
		mij.first = (A[i].first + A[i+1].first) * 0.5;
		mij.second = (A[i].second + A[i+1].second) * 0.5;

		if (egal(A[i].second, A[i+1].second))
		{
			aux.first = mij.first;
			aux.second = INF;
			
			int q1 = nr_inter_vert(aux, mij, i);
			
			if (!(q1 & 1)) aux.second = -INF;
			smn = semn(aux, A[i], A[i+1]);
		}
		else
		{
			aux.second = mij.second;
			aux.first = INF;

			int q1 = nr_inter_oriz(aux, mij, i);

			if (!(q1 & 1)) aux.first = -INF;
			smn = semn(aux, A[i], A[i+1]);
		}

		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;
	printf("%0.2lf\n", DABS(ar));

fclose(stdin);
fclose(stdout);
return 0;
}