Cod sursa(job #236469)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 27 decembrie 2008 17:52:20
Problema Camera Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 kb
#include<stdio.h>
#define N 2010
int n,i,j,nv,min_minus,min_plus,max_minus,max_plus,nv_copy;
double a[N],b[N],sac[N<<1],sbc[N<<1],san[N<<1],sbn[N<<1],*ac,*bc,*an,*bn,*aa,*ba,A1,B1,A2,B2,
epsilon=0.000001,aria;
void readd(),solve(),revers();
int is_trig(),poz(int ii);
int main()
{
	readd();
	solve();
	return 0;
}
void readd()
{
	freopen("camera.in","rt",stdin);
	freopen("camera.out","wt",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{ scanf("%lf%lf",&a[i],&b[i]);
	  a[i]=a[i]+100000;
	  b[i]=b[i]+100000;
	}
	a[n+1]=a[1];b[n+1]=b[1];
}
void solve()
{       double AA1,AA2,BB1,BB2,a11,a12,a21,a22,b1,b2,DX,DY,D;
	if(!is_trig())revers();
	nv=4;ac=&sac[0];bc=&sbc[0];an=&san[0];bn=&sbn[0];
	ac[1]=100000;bc[1]=100000;
	ac[2]=200000;bc[2]=100000;
	ac[3]=200000;bc[3]=200000;
	ac[4]=100000;bc[4]=200000;
	for(i=1;i<=n;i++)
	{
	  A1=a[i];B1=b[i];A2=a[i+1];B2=b[i+1];
	  min_plus=min_minus=max_plus=max_minus=0;
	  for(j=1;j<=nv;j++)
	  { if(poz(j)>=0)
	    { max_plus=j;
	      if(!min_plus)min_plus=j;
	    }
	    else
	    { max_minus=j;
	      if(!min_minus)min_minus=j;
	    }
	  }
	  if(!max_minus)continue;
	  ac[0]=ac[nv];bc[0]=bc[nv];
	  ac[nv+1]=ac[1];bc[nv+1]=bc[1];
	  nv_copy=nv;nv=0;
	  if(min_minus==1||max_minus==nv_copy)
	  { for(j=min_plus-1;j<=max_plus+1;j++)
	    { an[++nv]=ac[j];bn[nv]=bc[j];}
	  }
	  else
	  { for(j=max_minus;j<=nv_copy;j++)
	    { an[++nv]=ac[j];bn[nv]=bc[j];}
	    for(j=1;j<=min_minus;j++)
	    { an[++nv]=ac[j];bn[nv]=bc[j];}
	  }
	  a11=B1-B2;a12=A2-A1;b1=A2*B1-B2*A1;
	  AA1=an[1];BB1=bn[1];
	  AA2=an[2];BB2=bn[2];
	  a21=BB1-BB2;a22=AA2-AA1;b2=AA2*BB1-BB2*AA1;
	  DX=b1*a22-b2*a12;DY=a11*b2-a21*b1;
	  D=a11*a22-a12*a21;
	  an[1]=DX/D;bn[1]=DY/D;
	  AA1=an[nv-1];BB1=bn[nv-1];
	  AA2=an[nv];BB2=bn[nv];
	  a21=BB1-BB2;a22=AA2-AA1;b2=AA2*BB1-BB2*AA1;
	  DX=b1*a22-b2*a12;DY=a11*b2-a21*b1;
	  D=a11*a22-a12*a21;
	  an[nv]=DX/D;bn[nv]=DY/D;
	  aa=ac;ac=an;an=aa;
	  ba=bc;bc=bn;bn=ba;
	}
	aria=0;ac[nv+1]=ac[1];bc[nv+1]=bc[1];
	for(i=1;i<=nv;i++)
	 aria=aria+(ac[i]-ac[i+1])*(bc[i+1]+bc[i]);
	printf("%.2lf\n",aria/2);
}
int is_trig()
{     for(i=1;i<=n;i++)
       aria=aria+(a[i+1]-a[i])*(b[i+1]+b[i]);
      if(aria<0) return 1;
      return 0;
}
void revers()
{       int l,r;
	double aux;
	for(l=1,r=n+1;l<r;l++,r--)
	{ aux=a[l];a[l]=a[r];a[r]=aux;
	  aux=b[l];b[l]=b[r];b[r]=aux;
	}
}
int poz(int ii)
{
	double det;
	det=A1*B2+A2*bc[ii]+ac[ii]*B1-B1*A2-B2*ac[ii]-bc[ii]*A1;
	if(det>=-epsilon)return 1;
	if(det<-epsilon)return -1;
	return 1;
}