Cod sursa(job #644766)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 7 decembrie 2011 17:57:02
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include<stdio.h>
#include<set>
using namespace std;

#define eps 0.001
#define INF 1000000005
#define mp make_pair
#define minim(a,b) (a<b ? a : b)
#define maxim(a,b) (a>b ? a : b)
#define pi pair<double,double>
#define x first
#define y second
#define NMAX 5004

int n,nc,np;
double aria;
pi p[NMAX],c[NMAX],v[NMAX];

void get_coef(pi A, pi B, double &a, double &b, double &c)
{
	a=A.y-B.y;
	b=B.x-A.x;
	c=A.x*B.y-A.y*B.x;
}

int semn(pi A,pi B,pi C)
{
	double a, b, c;
	get_coef(A,B,a,b,c);
	double val=a*C.x+b*C.y+c;
	if(val+eps<0)
		return -1;
	else if(val-eps>0)
		return 1;
	return 0;		
}

pi intersect(pi A,pi B,pi C,pi D)
{
	double a1,b1,c1;
	double a2,b2,c2;
	
	get_coef(A,B,a1,b1,c1);
	get_coef(C,D,a2,b2,c2);
	
	return mp(
		(b1*c2-b2*c1)/(a1*b2-b1*a2),
		(a1*c2-a2*c1)/(a2*b1-a1*b2));
}

void tetau(pi A,pi B)
{
	int i,s1,s2;
		
	nc=0;
//	printf("? %.2lf %.2lf %.2lf %.2lf\n", A.x, A.y, B.x, B.y);
	for(i=1;i<=np;i++)
	{
		s1=semn(A,B,p[i]);
		s2=semn(A,B,p[i+1]);
		
		// printf(": %d %d\n", s1, s2);
		/*if(A.x==5 && A.y==5)
			printf("%d %d\n",s1,s2);*/
		if(s1==s2 && s1==-1)
			continue;
		if(s1>=0)
			c[++nc]=p[i];
		if(s1==1 && s2==-1)
			c[++nc]=intersect(A,B,p[i],p[i+1]);
		if(s1==-1 && s2==1)
			c[++nc]=intersect(A,B,p[i],p[i+1]);
	}	
}

double solve()
{
	int i,j,xmin=INF,xmax=-INF,ymin=INF,ymax=-INF;
	double aria=0.;

	for (i=1;i<=n;i++)
	{	
		xmin=minim(xmin,v[i].x);
		xmax=maxim(xmax,v[i].x);
		ymin=minim(ymin,v[i].y);
		ymax=maxim(ymax,v[i].y);
	}
	
	p[1]=mp(xmin,ymin);
	p[2]=mp(xmax,ymin);
	p[3]=mp(xmax,ymax);
	p[4]=mp(xmin,ymax);
	p[5]=p[1];
	np=4;
	
	for(i=1;i<=n;i++)
	{
/*		printf("////////////\n");
		for(j=1;j<=np;j++)
			printf("%.2lf %.2lf\n",p[j].x,p[j].y);
		printf("////////////\n\n");		
*/

		tetau(v[i],v[i+1]);
		np=nc;
		for(j=1;j<=nc;j++)
			p[j]=c[j];
		p[nc+1]=p[1];
		
		if (np<=2)
			return 0;
	}
	for(i=1;i<=np;i++)
		aria+=(p[i].y+p[i+1].y)*(p[i+1].x-p[i].x);
	if (aria < -eps)	
		aria = -aria;
	
	return aria*0.5;
}

int main ()
{
	int i,xx,yy,st,dr;
	pi aux;
	
	freopen("camera.in","r",stdin);
	freopen("camera.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&xx,&yy);
		v[i]=mp(xx,yy);
	}	
	v[n+1]=v[1];
	
	aria=solve();
	if (aria < eps)
	{
		st=1;dr=n;
		while (st<dr)
		{
			aux=v[st]; v[st]=v[dr]; v[dr]=aux;
			st++; dr--;
		}
		v[n+1]=v[1];
		
		aria=solve();
	}
		
	printf("%.2lf\n",aria);
	return 0;
}