Cod sursa(job #2457)

Utilizator wefgefAndrei Grigorean wefgef Data 17 decembrie 2006 11:48:21
Problema Camera Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.69 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

#define x first
#define y second
#define mp(a, b) make_pair(a, b)
#define punct pair<double, double>

#define eps 0.00000000001
#define inf 1000000 // o suta de mii
#define Nmax 10096

punct u[Nmax], t[Nmax], v[Nmax];
double rez;
int n, cont = -1;

void readdata()
{
	freopen("camera.in", "r", stdin);
	freopen("camera.out", "w", stdout);
	
	int i;
	
	scanf("%d", &n);
	for (i = 0; i < n; ++i)
		scanf("%lf %lf", &v[i].x, &v[i].y);
	v[n] = v[0];
}

double sign(punct a, punct b, punct c)
{
	long double val = a.x*b.y + b.x*c.y + c.x*a.y - c.x*b.y - a.x*c.y - b.x*a.y;
	if (fabs(val) < eps) return 0;
	if (val > eps) return 1;
	if (val < eps) return -1;
	return -1;
}

double arie()
{
	int i;
	double rez = 0;
	for (i = 0; i < n; ++i)
		rez += v[i].x*v[i+1].y - v[i].y*v[i+1].x;
	return rez;
}

punct intersect(punct a, punct b, punct c, punct d)
{
	double a1, b1, c1, a2, b2, c2, X = -inf, Y = -inf;
	
	if (a.x == b.x) X = a.x;
	if (c.x == d.x) X = c.x;
	if (a.y == b.y) Y = a.y;
	if (c.y == d.y) Y = c.y;
	
	a1 = b.y-a.y;
	b1 = a.x-b.x;
	c1 = a.y*(a.x-b.x) + a.x*(b.y-a.y);
	a2 = d.y-c.y;
	b2 = c.x-d.x;
	c2 = c.y*(c.x-d.x) + c.x*(d.y-c.y);	
	
	if (Y == -inf)
	Y = (c1 - a1*c2/a2)/(b1-a1*b2/a2);
	if (X == -inf)
	X = (c1-Y*b1)/a1;
	return mp(X, Y);
}

void solve()
{
	int semn, i, j, cur, next, nr;
	double  minx = inf, maxx = -inf, miny = inf, maxy = -inf, s1, s2;
	
	if (arie() > 0) semn = 1; else semn = -1;
	for (i = 0; i < n; ++i)
	{
		if (v[i].x < minx) minx = v[i].x;
		if (v[i].x > maxx) maxx = v[i].x;
		if (v[i].y < miny) miny = v[i].y;
		if (v[i].y > maxy) maxy = v[i].y;
	}
	cont = 3;
	u[0] = mp(minx, miny);
	u[1] = mp(maxx, miny);
	u[2] = mp(maxx, maxy);
	u[3] = mp(minx, maxy);
		
	for (i = 0; i < n; ++i)
	{
		cur = 0; next = 1;
		nr = -1;
		if (cont >= 2)
		do
		{
			s1 = sign(v[i], v[i+1], u[cur]);
			s2 = sign(v[i], v[i+1], u[next]);
			if (s1 != -semn && s2 != -semn) 
				t[++nr] = u[next];
			if (s1 != -semn && s2 == -semn) 
				t[++nr] = intersect(v[i], v[i+1], u[cur], u[next]);
			if (s1 == -semn && s2 != -semn)
			{
				t[++nr] = intersect(v[i], v[i+1], u[cur], u[next]);
				t[++nr] = u[next];
			}
			++cur; if (cur > cont) cur = 0;
			++next; if (next > cont) next = 0;
		}
		while (cur != 0);		
		
		for (j = 0; j <= nr; ++j)
			u[j] = t[j];
		cont = nr;
	}
	if (cont < 2) return;
	u[cont+1] = u[0];
	for (i = 0; i <= cont; ++i)
		rez += u[i].x*u[i+1].y - u[i].y*u[i+1].x;
	rez = fabs(rez)/2;
}

void writedata()
{
	printf("%.2lf\n", rez);
}

int main()
{
	readdata();
	solve();
	writedata();
	return 0;
}