Cod sursa(job #599805)

Utilizator ChallengeMurtaza Alexandru Challenge Data 29 iunie 2011 17:15:56
Problema Camera Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <fstream>
#include <iomanip>

using namespace std;

const char InFile[]="camera.in";
const char OutFile[]="camera.out";
const int MaxN=1024;
const int MaxK=MaxN<<1;
const double FINF=1.e64;
const double EPS=1e-6;

ifstream fin(InFile);
ofstream fout(OutFile);

struct Point2D
{
	Point2D(double x=0, double y=0):x(x),y(y){};
	
	double x,y;
};

int N,K,sign;
Point2D p[MaxN],k[MaxK],tmp[MaxK];
Point2D O(0,0);

inline double myabs(const double &a)
{
	if(a<0)
	{
		return -a;
	}
	return a;
}

inline int cmp(const double &a,  const double &b)
{
	if(a+EPS<b)
	{
		return -1;
	}
	if(b+EPS<a)
	{
		return 1;
	}
	return 0;
}

inline int nextN(const int &index)
{
	if(index==N)
	{
		return 1;
	}
	return index+1;
}

inline int nextK(const int &index)
{
	if(index==K)
	{
		return 1;
	}
	return index+1;
}

inline double det(const Point2D &A, const Point2D &B, const Point2D &C)
{
	return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}

inline int sgn(const double &x)
{
	return cmp(x,0);
}

inline void coef(const Point2D &A, const Point2D &B, double &a, double &b, double &c)
{
	a=B.y-A.y;
	b=A.x-B.x;
	c=A.y*B.x-A.x*B.y;
}

inline Point2D intersect(const Point2D &A1, const Point2D &A2, const Point2D &B1, const Point2D &B2)
{
	double a1,b1,c1;
	double a2,b2,c2;
	coef(A1,A2,a1,b1,c1);
	coef(B1,B2,a2,b2,c2);
	return Point2D((b1*c2-b2*c1)/(a1*b2-a2*b1),
				   (c1*a2-a1*c2)/(a1*b2-a2*b1));
}

inline void cut(const Point2D &A, const Point2D &B)
{
	int t=0;
	for(register int i=1;i<=K;++i)
	{
		int ni=nextK(i);
		int s1=sgn(det(A,B,k[i]));
		int s2=sgn(det(A,B,k[ni]));
		if(s1==sign || s1==0)
		{
			tmp[++t]=k[i];
		}
		if(s1!=s2 && s1!=0 && s2!=0)
		{
			tmp[++t]=intersect(A,B,k[i],k[ni]);
		}
	}
	K=t;
	for(register int i=1;i<=K;++i)
	{
		k[i]=tmp[i];
	}
}

inline double ka()
{
	for(register int i=1;i<=N;++i)
	{
		cut(p[i],p[nextN(i)]);
		if(K<3)
		{
			return 0;
		}
	}

	double sol=0;
	for(register int i=1;i<=K;++i)
	{
		sol+=det(O,k[i],k[nextK(i)]);
	}
	return myabs((double)sol)*0.5;
}

int main()
{
	double xmin=FINF,ymin=FINF,xmax=-FINF,ymax=-FINF;
	fin>>N;
	for(register int i=1;i<=N;++i)
	{
		fin>>p[i].x>>p[i].y;
		xmin=min(xmin,p[i].x);
		xmax=max(xmax,p[i].x);
		ymin=min(ymin,p[i].y);
		ymax=max(ymax,p[i].y);
	}
	fin.close();

	k[4]=Point2D(xmin,ymin);
	k[3]=Point2D(xmin,ymax);
	k[2]=Point2D(xmax,ymax);
	k[1]=Point2D(xmax,ymin);
	K=4;

	int t=sgn(det(O,k[1],k[2])+det(O,k[2],k[3])+det(O,k[3],k[4])+det(O,k[4],k[1]));

	double area=0;
	for(register int i=1;i<=N;++i)
	{
		area+=det(O,p[i],p[nextN(i)]);
	}

	sign=sgn(area);
	double sol=ka();
	sign=-sign;
	sol=max(sol,ka());
	fout<<setprecision(2)<<fixed<<sol;
	fout.close();
	return 0;
}