Cod sursa(job #374036)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 15 decembrie 2009 19:39:03
Problema Camera Scor 10
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.9 kb
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

#define file_in "camera.in"
#define file_out "camera.out"

#define Nmax 2222

#define eps 1e-3
#define x first
#define y second
#define mp make_pair
#define pdd pair <double,double>
#define Inf 10000000 

int n;
pdd p[Nmax],v[Nmax],sol[Nmax];
int cur,next;
int s,semn1,semn2;
double maxx,maxy,minx,miny;


int semn(pdd a, pdd b, pdd c)
{
	double d=a.x*b.y+b.x*c.y*c.x*b.y-c.x*a.y-a.x*c.y-b.x*a.y;

	if (fabs(d)<eps) return 0;
	if (d>0)
		return 1;
	else
	if (d==0)
		return 0;
	else
        return -1;
}


pdd intersect(pdd a, pdd b, pdd c, pdd d)
{
	
	pdd dd;
	
	double a1,a2,b1,b2,c1,c2;
	
	a1=a.y-b.y;
	a2=c.y-d.y;
	
	b1=a.x-b.x;
	b2=c.x-d.x;
	
	c1=a.x*b.y-b.x*a.y;
	c2=c.x*d.y-d.x*c.y;
	
	dd.x=(b1*c2-b2*c1)/(a1*b2-a2*b1);
	dd.y=(c1*a2-c2*a1)/(a1*b2-a2*b1);
	
	return d;
}



double aria()
{
	double arie=0;
	int i;
	
	for (i=0;i<n;++i)
		 arie+=(p[i].x*p[i+1].y-p[i].y*p[i+1].x);
	return arie;
}



int main()
{
	int i,j,nr,nrp;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &n);
	
	for (i=0;i<n;++i)
		 scanf("%lf %lf", &p[i].x, &p[i].y);
	
	p[n]=p[0];
	
	if (aria()>0)
	    s=-1;
	else
		s=1;
	
	maxx=maxy=-Inf;
	minx=miny=Inf;
	for (i=0;i<n;++i)
	{
		if (p[i].x>maxx)
			maxx=p[i].x;
		if (p[i].x<minx)
			minx=p[i].x;
		if (p[i].y>maxy)
			maxy=p[i].y;
		if (p[i].y<miny)
			miny=p[i].y;
	}
	
	v[0]=mp(minx,miny);
	v[1]=mp(maxx,miny);
	v[2]=mp(maxx,maxy);
	v[3]=mp(minx,maxy);
	v[4]=v[1];
	nr=3;
	
	/*	for (j=0;j<=nr;++j)
			 printf("%.2lf %.2lf\n", v[j].x, v[j].y);*/
	
	for (i=0;i<n;++i)
	{
		nrp=-1;
		for (j=0;j<nr;++j)
		{
			semn1=semn(p[i],p[i+1],v[cur]);
		    semn2=semn(p[i],p[i+1],v[next]);
			
			if (semn1!=s && semn2!=s)//ambele sunt in interior
			{
				sol[++nrp]=v[next];//adaug punctul urmator
			}
			if (semn1!=s && semn2==s)//punctul curent e in interior punctul urmator e in exterior
		    {
				sol[++nrp]=intersect(p[i],p[i+1],v[cur],v[next]);//adaug punctul de intersectie
			}
			if (semn1==s && semn2!=s)//punctul curent e in exterior punctul urmator e in interior
			{
				sol[++nrp]=intersect(p[i],p[i+1],v[cur],v[next]);//adaug punctul de intersectie
				sol[++nrp]=v[next];//adaug si punctul urmator
			}
			//daca ambele sunt in exterior trec mai departe
		}
		
		//reactualizez
		for (j=0;j<nrp;++j)
			 v[j]=sol[j];
		v[nrp]=v[0];
		nr=nrp;
		/*for (j=0;j<=nrp;++j)
			 printf("%.2lf %.2lf\n", sol[j].x, sol[j].y);
		printf("\n");*/
	}
		
	/*printf("\n");*/

    		
	double res=0;
	v[nr]=v[0];
	for (i=0;i<nr;++i) 
        // printf("%.2lf %.2lf\n", v[i].x, v[i].y); 
		res+=v[i].x*v[i+1].y-v[i].y*v[i+1].x; 
	res=fabs(res)/2.0; 

	
	printf("%.2lf\n", res);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}