Cod sursa(job #784329)

Utilizator danalex97Dan H Alexandru danalex97 Data 5 septembrie 2012 15:44:06
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <fstream>
#include <iomanip>
#include <cmath>

using namespace std;

#define x first
#define y second

const int Nmax = 10010;
const int oo = 100010;
#define EPS 0.000001

ifstream F("camera.in");
ofstream G("camera.out");

typedef pair<double,double> Pair;

Pair A[Nmax],B[Nmax],C[Nmax];

double Sol;
int Semn,N,M,P;

double Aria(Pair A[],int N)
{
	double Sum=0;
	for (int i=1;i<=N;++i)
		Sum+=A[i].x*A[i+1].y-A[i+1].x*A[i].y;
	return Sum/2;
}

int Sign(Pair A, Pair B, Pair C)
{
	double a = A.y - B.y;
	double b = B.x - A.x;
	double c = - B.x * A.y + B.y * A.x;
	
	if ( a*C.x+b*C.y+c > -EPS ) return 1;
	if ( a*C.x+b*C.y+c < EPS ) return -1;
	
	return 0;
}

Pair Int (Pair P, Pair Q, Pair R, Pair S)
{
    double A1,B1,C1,A2,B2,C2,D;

    A1=1.0*Q.y-P.y;
    B1=P.x-Q.x;
    C1=A1*P.x+B1*P.y;

    A2=1.0*S.y-R.y;
    B2=R.x-S.x;
    C2=A2*R.x+B2*R.y;

    D=A1*B2-A2*B1;

    if (fabs(D)<EPS)
        return make_pair(-2*oo,-2*oo);

    return make_pair((B2*C1-B1*C2)/D,(A1*C2-A2*C1)/D);
}


int main()
{
	F>>N; 
	for (int i=1;i<=N;++i) 
		F>>A[i].x>>A[i].y;
	A[N+1]=A[1];
	
	Semn=( Aria(A,N)>0 ) ? +1 : -1;

	M=4;
	B[1]=make_pair(-oo,+oo);
	B[2]=make_pair(+oo,+oo);
	B[3]=make_pair(+oo,-oo);
	B[4]=make_pair(-oo,-oo);
	B[5]=make_pair(-oo,+oo);
	
	for (int i=1;i<=N;++i)
	{
		int Act,Next;
		
		P=0;
		if ( M<3 )
		{
			G<<0<<'\n';
			return 0;
		}
		
		for (Act=1;Act<=M;++Act)
		{
			Next=Act+1;
			int S1 = Sign(A[i],A[i+1],B[Act]);
			int S2 = Sign(A[i],A[i+1],B[Next]);
			
			if (S1 != -Semn && S2 != -Semn) 
				C[++P] = B[Next];
			if (S1 != -Semn && S2 == -Semn) 
				C[++P] = Int(A[i], A[i+1], B[Act], B[Next]);
			if (S1 == -Semn && S2 != -Semn) 
				C[++P] = Int(A[i], A[i+1], B[Act], B[Next]),
				C[++P] = B[Next];
			
			if ( P>1 )
				if ( C[P-1].x == -2*oo || C[P-1].y == -2*oo ) swap(C[P-1],C[P]),--P;
			if ( P>0 )
				if ( C[P].x == -2*oo || C[P].y == -2*oo ) --P;
		}
		
		M=P;
		for (int i=1;i<=M;++i) B[i]=C[i];
		B[M+1]=B[1];
	}
	
	Sol = Aria(B,M) ;
	G<< fixed << setprecision(2) << fabs(Sol)<<'\n';
}