Cod sursa(job #592930)

Utilizator tiganu_dolarMancea Catalin tiganu_dolar Data 31 mai 2011 14:59:55
Problema Camera Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 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;
	for(i=1;i<=np;i++)
	{
		s1=semn(A,B,p[i]);
		s2=semn(A,B,p[i+1]);
		/*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]);
	}	
}

int main ()
{
	int i,j,xx,yy,xmin=INF,xmax=-INF,ymin=INF,ymax=-INF,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);
		xmin=minim(xmin,v[i].x);
		xmax=maxim(xmax,v[i].x);
		ymin=minim(ymin,v[i].y);
		ymax=maxim(ymax,v[i].y);
	}	
	if(semn(v[1],v[2],v[3])>0)
	{
		st=1;dr=n;
		while(st<=dr)
		{
			aux=v[st];
			v[st]=v[dr];
			v[dr]=aux;
			st++;
			dr--;
		}
	}
	v[n+1]=v[1];
	
	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++)
	{
		tetau(v[i],v[i+1]);
		np=nc;
		for(j=1;j<=nc;j++)
			p[j]=c[j];
		p[nc+1]=p[1];
	}
	for(i=1;i<=np;i++)
		aria+=(p[i].y+p[i+1].y)*(p[i+1].x-p[i].x);
	if(aria+eps<0)
		aria=-aria;	
	printf("%.2lf\n",aria*0.5);
	return 0;
}