Cod sursa(job #114520)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 14 decembrie 2007 17:46:39
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector< pair<double, double> > pol, p, newp;

#define x first
#define y second
#define EPS 1e-5
#define INF 1e10

inline void getCoef( double &A, double &B, double &C, const pair<double, double> &a, const pair<double, double> &b )
{
	A = b.y - a.y;
	B = a.x - b.x;
	C = a.y * b.x - a.x * b.y;
}

inline int sign( double A, double B, double C, const pair<double, double> pct )
{
	double D = A * pct.x + B * pct.y + C;
	if (D > EPS) return 1;
	if (D < -EPS) return -1;
	return 0;
}

pair<double, double> intersect( double A1, double B1, double C1, const pair<double, double> pct1, const pair<double, double> pct2 )
{
	double A2, B2, C2;
	getCoef( A2, B2, C2, pct1, pct2 );
	
	double det = A1 * B2 - A2 * B1;
	double X = (B1 * C2 - B2 * C1) / det;
	double Y = (A2 * C1 - A1 * C2) / det;

	return make_pair(X, Y);
}

inline double getArea()
{
	p.clear();
	p.push_back( make_pair( -INF, -INF ) );
	p.push_back( make_pair( -INF,  INF ) );
	p.push_back( make_pair(  INF,  INF ) );
	p.push_back( make_pair(  INF, -INF ) );
	p.push_back( p.front() );

	for (int i = 0; i < N; i++)
	{
		double A, B, C;
		getCoef( A, B, C, pol[i], pol[i + 1] );
		
		newp.clear();
		for (size_t k = 0; k + 1 < p.size(); k++)
		{
			int sgnCur, sgnNxt;
			sgnCur = sign( A, B, C,     p[k] );
			sgnNxt = sign( A, B, C, p[k + 1] );

			if (sgnCur >= 0 && sgnNxt >= 0)
				newp.push_back( p[k] );
			if (sgnCur < 0 && sgnNxt >= 0)
				newp.push_back( intersect( A, B, C, p[k], p[k + 1] ) );
			if (sgnCur >= 0 && sgnNxt < 0)
			{
				newp.push_back( p[k] );
				if (sgnCur > 0)
					newp.push_back( intersect( A, B, C, p[k], p[k + 1] ) );
			}
			if (sgnCur < 0 && sgnNxt < 0)
				continue;
		}
		newp.push_back( newp.front() );
		p = newp;
	}

	double S = 0;
	for (size_t k = 0; k + 1 < p.size(); k++)
		S += p[k].x * p[k + 1].y - p[k].y * p[k + 1].x;
	S = fabs(S) * 0.5;
	return S;
}

int main()
{
	freopen("camera.in", "rt", stdin);
	freopen("camera.out", "wt", stdout);


	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		double X, Y;
		scanf("%lf %lf", &X, &Y);
		pol.push_back( make_pair(X, Y) );
	}
	pol.push_back( pol.front() );

	double S = getArea();
	if (S < EPS)
	{
		reverse( pol.begin(), pol.end() );
		S = getArea();
	}
	printf("%.2lf\n", S);
	return 0;
}