Cod sursa(job #654149)

Utilizator crushackPopescu Silviu crushack Data 29 decembrie 2011 18:15:46
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <stdio.h>
#include <algorithm>
#define NMax 5010
#define eps 0.001
using namespace std;

const char IN[]="camera.in",OUT[]="camera.out";

struct point{
	double x,y;
};

int N , np ;
point p[NMax],c[NMax],v[NMax];
const double oo = 1e10;

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

int sgn(point const &A,point const &B,point const &C)
{
	static double a,b,c;
	coef(A,B,a,b,c);
	double v=a*C.x+b*C.y+c;
	return  (v+eps<0) ? -1 : ((v-eps>0) ? 1 : 0 );
}

point intersect(point const &A,point const &B,point const &C,point const &D)
{
	static point ret;
	static double a1,b1,c1,a2,b2,c2;
	coef(A,B,a1,b1,c1);
	coef(C,D,a2,b2,c2);
	ret.x=(b1*c2 - b2*c1)/(a1*b2 - a2*b1);
	ret.y=(a1*c2 - a2*c1)/(a2*b1 - a1*b2);
	return ret;
}

int Update(point const &A,point const &B)
{
	int i,s1,s2;
	int n=0;
	for (i=1;i<=np;++i)
	{
		s1=sgn(A,B,p[i]);
		s2=sgn(A,B,p[i+1]);
		if ( s1==-1 && s2==-1 )
			continue;
		if ( s1>= 0 )
			c[++n]=p[i];
		if ( s1==-1 && s2==1 || s1==1 && s2==-1 )
			c[++n]=intersect(A,B,p[i],p[i+1]);
	}
	return n;
}

double solve()
{
	int i,j;double xmin=oo,xmax=-oo,ymin=oo,ymax=-oo;double ret=0;
	for (i=1;i<=N;++i)
	{
		xmin=min(xmin,v[i].x);
		xmax=max(xmax,v[i].x);
		ymin=min(ymin,v[i].y);
		ymax=max(ymax,v[i].y);
	}
	p[1].x= xmin ; p[1].y= ymin;
	p[2].x= xmax ; p[2].y= ymin;
	p[3].x= xmax ; p[3].y= ymax;
	p[4].x= xmin ; p[4].y= ymax;
	p[5]=p[1];
	np=4;
	for (i=1;i<=N;++i)
	{
		np=Update(v[i],v[i+1]);
		for (j=1;j<=np;++j)
			p[j]=c[j];
		p[np+1]=p[1];
		if (np<=2) return 0;
	}
	p[0]=p[np];
	for (i=1;i<=np;++i)
		ret+= (p[i].y+p[i+1].y)*(p[i+1].x-p[i].x);
	if (ret<-eps) ret=-ret;
	return ret*0.5;
}

int main()
{
	int i,x,y;double tmp;
	freopen(IN,"r",stdin);
	scanf("%d",&N);
	for (i=1;i<=N;++i)
		scanf("%d%d",&x,&y),
		v[i].x=x,v[i].y=y;
	fclose(stdin);
	v[N+1]=v[1];
	
	double sol=solve();
	if (sol<eps)
	{
		for (int st=1,dr=N;st<dr;++st,--dr)
			swap(v[st],v[dr]);
		v[N+1]=v[1];
		sol=solve();
	}
	
	freopen(OUT,"w",stdout);
	printf("%.2lf\n",sol);
	fclose(stdout);
	
	return 0;
}