Cod sursa(job #117251)

Utilizator alextheroTandrau Alexandru alexthero Data 20 decembrie 2007 23:57:21
Problema Camera Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

#define inf 1000000
#define nmax 1505
#define pb push_back

using namespace std;
typedef pair<double, double> dd;

int n, T;
double ar;
dd pt[nmax];
vector <dd> rez, nr;

inline double absol(double x)
{
	if(x < 0) return -x;
	else return x;
}

void init()
{
	rez.clear();
	rez.pb(dd(-inf, -inf));
	rez.pb(dd(-inf, inf));
	rez.pb(dd(inf, inf));
	rez.pb(dd(inf, -inf));
}

inline dd intersect(dd p1, dd p2, dd p3, dd p4)
{
	double a1 = p2.second - p1.second;
	double b1 = p1.first - p2.first;
	double c1 = a1 * p1.first + b1 * p1.second;

	double a2 = p4.second - p3.second;
	double b2 = p3.first - p4.first;
	double c2 = a2 * p3.first + b2 * p3.second;

	double det = a1 * b2 - a2 * b1;
	if(det == 0) return dd(inf, inf);
	else return dd((double)(b2 * c1 - b1 * c2) / det, (double)(a1 * c2 - a2 * c1) / det);
}

inline double cp(dd p1, dd p2, dd p3)
{
	double x1 = p2.first - p1.first;
	double y1 = p2.second - p1.second;
	double x2 = p3.first - p1.first;
	double y2 = p3.second - p1.second;
	
	return (double)x1 * y2 - x2 * y1;
}

void calc()
{
	for(int i = 1; i <= n; i++)
	{
		nr.clear();
		rez.pb(rez[0]);

		for(int j = 0; j < (int)rez.size() - 1; j++)
		{
			if(cp(pt[i], pt[i + 1], rez[j]) > 0)
			{
				if(cp(pt[i], pt[i + 1], rez[j + 1]) < 0)
					nr.pb(intersect(rez[j], rez[j + 1], pt[i], pt[i + 1]));
			}
			else
			{
				nr.pb(rez[j]);
				if(cp(pt[i], pt[i + 1], rez[j + 1]) > 0)
					nr.pb(intersect(rez[j], rez[j + 1], pt[i], pt[i + 1]));
			}
		}
		rez = nr;
	}
}

double arie(vector <dd> a)
{
	double ar = 0;
	for(int i = 1; i < (int)a.size() - 1; i++)
	{
		double x1 = a[i].first - a[0].first;
		double y1 = a[i].second - a[0].second;
		double x2 = a[i + 1].first - a[0].first;
		double y2 = a[i + 1].second - a[0].second;
		double cr = x1 * y2 - x2 * y1;
		ar += cr;
	}

	return absol(ar / 2.0);
}

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

	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%lf%lf", &pt[i].first, &pt[i].second);
	pt[n + 1] = pt[1];

	init();
	calc();
	ar = arie(rez);
	printf("%.2lf\n", ar);

	return 0;
}