Cod sursa(job #599848)

Utilizator ChallengeMurtaza Alexandru Challenge Data 29 iunie 2011 18:36:54
Problema Camera Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.89 kb
#include <fstream>
#include <iomanip>

using namespace std;

const char InFile[]="camera.in";
const char OutFile[]="camera.out";
const int MaxN=2048;
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>=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()
{
	Point2D A(20,10);
	Point2D B(21,10);
	Point2D C(-50,500);
	Point2D D(-500,500);
	Point2D I=intersect(A,B,C,D);

	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[1]=Point2D(xmin,ymin);
	k[2]=Point2D(xmin,ymax);
	k[3]=Point2D(xmax,ymax);
	k[4]=Point2D(xmax,ymin);
	K=4;

	double sol=ka();
	if(cmp(sol,0)<=0)
	{
		k[1]=Point2D(xmin,ymin);
		k[2]=Point2D(xmin,ymax);
		k[3]=Point2D(xmax,ymax);
		k[4]=Point2D(xmax,ymin);
		K=4;
		int st=1;
		int dr=N;
		while(st<dr)
		{
			swap(p[st],p[dr]);
			++st;
			--dr;
		}
		sol=ka();
	}
	fout<<setprecision(2)<<fixed<<sol;
	fout.close();
	return 0;
}