Cod sursa(job #385870)

Utilizator ErgoVicol Sergiu Constantin Ergo Data 23 ianuarie 2010 17:53:03
Problema Camera Scor 40
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.01 kb
#include <fstream>
#include <cstring>
#include <algorithm>
#include <cmath>

#define fmic 0.00000001
#define NMAX 2100
#define inf 100010

using namespace std;

struct punct { double x,y; };

int NP, NA, NF;

punct P[NMAX], A[NMAX], F[NMAX];


void citeste(void)
{
	ifstream fin("camera.in");
	int i;
	
	fin >>NP;
	for (i = 0; i < NP; i++)
		fin >>P[i].x >>P[i].y;
	P[NP] = P[0];
	
	fin.close();
}

inline double det(double x1, double y1, double x2, double y2, double x3, double y3)
{
	return (x1*y2 + x2*y3 + x3*y1 - x1*y3 - x2*y1 - x3*y2); 
}

inline double arie(int N, punct X[])
{
	int i;
	double area = 0.;
	
	for (i = 1; i < N-1; i++)
		area += det(X[0].x, X[0].y, X[i].x, X[i].y, X[i+1].x, X[i+1].y);
	
	return area;
}

inline int sign(double a)
{
	if (fabs(a) < fmic) return 0;
	if (a < 0) return -1;
	return 1;
}

inline punct intersect(punct a, punct b, punct c, punct d)
{
	double A1,B1,C1,A2,B2,C2;
	punct H;
	A1 = b.y-a.y; B1 = a.x-b.x; C1 = a.x*b.y- b.x*a.y;
	A2 = d.y-c.y; B2 = c.x-d.x; C2 = c.x*d.y- d.x*c.y;
	
	double det = A1*B2 - A2*B1;
    if(det != 0)
	{
        H.x = (B2*C1 - B1*C2)/det;
        H.y = (A1*C2 - A2*C1)/det;
    }
	return H;
}

void rezolva()
{
	A[0].x = A[1].x = A[0].y = A[3].y = -inf;
	A[1].y = A[2].x = A[2].y = A[3].x = inf;
	A[4] = A[0];
	NA = 4;
	
	int i, j, cur, next, semn;
	
	semn = sign(arie(NP, P));
	
	for (i = 0; i < NP; i++)
	{
		NF = 0;
		for (j = 0; j < NA; j++)
		{
			cur = sign(det(P[i].x, P[i].y, P[i+1].x, P[i+1].y, A[j].x, A[j].y));
			next = sign(det(P[i].x, P[i].y, P[i+1].x, P[i+1].y, A[j + 1].x, A[j + 1].y));
			
			if (cur == semn || cur == 0) F[NF++] = A[j];
			
			if (cur * next == -1) F[NF++] = intersect(P[i],P[i+1],A[j],A[j+1]);
			
		}
		NA = NF;
		memcpy(A,F,(NF+1)*sizeof(punct));
		A[NA] = A[0];	
	}
}

void afiseaza()
{
	ofstream fout("camera.out");

	fout <<fabs(arie(NA, A)/2.0);
	fout.close();
}

int main()
{
	citeste();
	
	rezolva();
	
	afiseaza();

	return 0;
}