Cod sursa(job #2273)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 16 decembrie 2006 18:38:09
Problema Camera Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <cstdio>
#include <cmath>
#include <vector>

using namespace std;

#define MAXN 2048

int N;
int x[MAXN], y[MAXN];

vector< pair<double, double> > pol, nxtpol;
vector< int > sgn;

#define EPS 1e-6
#define INF 1e+10

int semn(double A, double B, double C, double x, double y)
{
	double D = A * x + B * y + C;
	if (D < -EPS) return -1;
	if (D > EPS) return 1;
	return 0;
}

void getcoef(double x1, double y1, double x2, double y2, double &A, double &B, double &C)
{
	A = y1 - y2;
	B = x2 - x1;
	C = x1 * y2 - x2 * y1;
}

pair<double, double> get_intersection(double A1, double B1, double C1, pair<double, double> p1, pair<double, double> p2)
{
	double A2, B2, C2;
	getcoef(p1.first, p1.second, p2.first, p2.second, A2, B2, C2);
	double det = A1 * B2 - A2 * B1;
	if (det == 0)
		return make_pair(-INF, -INF);
	double x, y;
	x = (B1 * C2 - B2 * C1) / det;
	y = (A2 * C1 - A1 * C2) / det;
	return make_pair(x, y);
}

double getit()
{
	pol.clear(); sgn.clear();
	pol.push_back( make_pair(-INF, -INF) );
	pol.push_back( make_pair(-INF, INF) );
	pol.push_back( make_pair(INF, INF) );
	pol.push_back( make_pair(INF, -INF) );

	int i, j;
	double A, B, C; 
	for (i = 0; i < N; i++)
	{
		nxtpol.clear();
		sgn.resize( pol.size() + 1);
		getcoef(x[i], y[i], x[i + 1], y[i + 1], A, B, C);

		for (j = 0; j < (int)pol.size(); j++)
			sgn[j] = semn(A, B, C, pol[j].first, pol[j].second);
		sgn[ (int)pol.size() ] = sgn[0];

		for (j = 0; j < (int)pol.size(); j++)
		{
			pair<double, double> nxt = pol[ (j + 1) % ((int)pol.size()) ];
			if (sgn[j] <= 0 && sgn[j + 1] <= 0)
				nxtpol.push_back(nxt);
			if (sgn[j] <= 0 && sgn[j + 1] > 0)
				nxtpol.push_back( get_intersection( A, B, C, pol[j], nxt ) );
			if (sgn[j] > 0 && sgn[j + 1] > 0)
				continue;
			if (sgn[j] > 0 && sgn[j + 1] <= 0)
			{
				nxtpol.push_back( get_intersection( A, B, C, pol[j], nxt ) );
				nxtpol.push_back( nxt );
			}
		}
		pol = nxtpol;
	}

	double S = 0;
	pol.push_back( pol[0] );
	for (i = 0; i + 1 < (int) pol.size(); i++)
		S += pol[i].first * pol[i + 1].second - pol[i + 1].first * pol[i].second;
	return fabs(S / 2);
}

int main()
{
	freopen("camera.in", "rt", stdin);
	freopen("camera.out", "wt", stdout);
	int i, j;
	for (scanf("%d", &N), i = 0; i < N; i++)
		scanf("%d %d", x + i, y + i);
	x[N] = x[0]; y[N] = y[0];
	double rez = getit();
	if (fabs(rez) < EPS)
	{
		for (i = 0, j = N - 1; i < j; i++, j--)
		{
			int tmp = x[i]; x[i] = x[j]; x[j] = tmp;
			tmp = y[i]; y[i] = y[j]; y[j] = tmp;
		}
		rez = getit();
	}
	printf("%.2lf\n", rez);
	return 0;
}