Cod sursa(job #72856)

Utilizator moga_florianFlorian MOGA moga_florian Data 15 iulie 2007 17:53:11
Problema Camera Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.56 kb
#include<stdio.h>
#include<math.h>
#define Nmax 2005
#define eps .000001

int N,X[Nmax],Y[Nmax],N1,N2;
double X1[Nmax],Y1[Nmax],X2[Nmax],Y2[Nmax];
double ang[Nmax];

int main()
{
FILE *fin=fopen("camera.in","r"),
     *fout=fopen("camera.out","w");
     
int i,j,k,Xmin=100000,Xmax=-100000,Ymin=100000,Ymax=-100000;
double gx,gy,aux;
gx=gy=0.0;
     
fscanf(fin,"%d",&N);
for(i=1;i<=N;i++)
  {
  fscanf(fin,"%d%d",&X[i],&Y[i]);
  gx+=(double) X[i];
  gy+=(double) Y[i];
  }
  
gx/=(double)N;
gy/=(double)N;
for(i=1;i<=N;i++)
   ang[i] = atan2 ((double)Y[i] - gy, (double)X[i] - gx);

//sort
for(i=1;i<=N;i++)
  {
  j=i;
  while(j/2 && ang[j/2] < ang[j])
      {
      aux=ang[j/2], ang[j/2]=ang[j],  ang[j]=aux;
      X[j/2]^=X[j], X[j]^=X[j/2], X[j/2]^=X[j];
      Y[j/2]^=Y[j], Y[j]^=Y[j/2], Y[j/2]^=Y[j];
      j>>=1;      
      }               
  }
  
i=N;
while(i>1)
 {
 aux=ang[1], ang[1]=ang[i], ang[i]=aux;
 X[1]^=X[i], X[i]^=X[1], X[1]^=X[i];
 Y[1]^=Y[i], Y[i]^=Y[1], Y[1]^=Y[i];
 i--;
     
 j=1;
 while(1)
   {
   k=j<<1;
   if(k>i) break;
   if(k+1 <= i && ang[k+1] > ang[k]) k++;
   if(ang[j] >= ang[k]) break;
   
   aux=ang[j], ang[j]=ang[k], ang[k]=aux;
   X[j]^=X[k], X[k]^=X[j], X[j]^=X[k];
   Y[j]^=Y[k], Y[k]^=Y[j], Y[j]^=Y[k];
   j=k;      
   }
 }
 
//solve
for(i=1;i<=N;i++)
  {
  if(X[i] < Xmin) Xmin=X[i];
  if(X[i] > Xmax) Xmax=X[i];
  
  if(Y[i] < Ymin) Ymin=Y[i];
  if(Y[i] > Ymax) Ymax=Y[i];               
  }

//init  

N1=4;
X1[1]=(double)Xmin; Y1[1]=(double)Ymax;
X1[2]=(double)Xmin; Y1[2]=(double)Ymin;
X1[3]=(double)Xmax; Y1[3]=(double)Ymin;
X1[4]=(double)Xmax; Y1[4]=(double)Ymax;

X[N+1]=X[1],Y[N+1]=Y[1];


//aflare poligon intersectie
double Xi,Yi,A1,B1,C1,vc,vu,A2,B2,C2,det;

for(i=1;i<=N;i++)
  {
  A1=(double)Y[i+1] - Y[i];
  B1=(double)X[i] - X[i+1];
  C1=A1*X[i]+B1*Y[i];
  //pentru a fi in interior -> <0
  
  N2=0;
  X1[N1+1]=X1[1]; Y1[N1+1]=Y1[1];    
  for(j=1;j<=N1;j++) 
     {
     vc=A1*X1[j]+B1*Y1[j]-C1;
     vu=A1*X1[j+1]+B1*Y1[j+1]-C1;
     
     if(vc<=eps && vu<=eps)
        {
        X2[++N2]=X1[j];
        Y2[N2]=Y1[j];     
        }
     else
     if(vc<=eps && vu > eps)
        {
        X2[++N2]=X1[j];
        Y2[N2]=Y1[j];     
        
        if( -vc > eps )
            {//punctul de intersectie
             A2=Y1[j+1]-Y1[j];
             B2=X1[j]-X1[j+1];
             C2=A2*X1[j] + B2*Y1[j];
             
             det= A1*B2 - A2*B1;             
             Xi= (B2*C1 - B1*C2) / det;
             Yi= (A1*C2 - A2*C1) / det;
             
             X2[++N2]=Xi;
             Y2[N2]=Yi;                             
            }        
        }
      else
      if(vc >= eps && vu <= eps)
         {//doar punctul de intersectie
             A2=Y1[j+1]-Y1[j];
             B2=X1[j]-X1[j+1];
             C2=A2*X1[j] + B2*Y1[j];
             
             det= A1*B2 - A2*B1;             
             Xi= (B2*C1 - B1*C2) / det;
             Yi= (A1*C2 - A2*C1) / det;
             
             X2[++N2]=Xi;
             Y2[N2]=Yi;                             
         }
     }                 
  
  N1=N2;
  for(j=1;j<=N1;j++) 
      X1[j]=X2[j], Y1[j]=Y2[j];   
  }
  
// aria poligonului rezultat
double area=0.0;
for(i=2;i<N1;i++)
   {
   A1= X1[i] - X1[1];
   B1= Y1[i] - Y1[1];
   A2= X1[i+1] - X1[1];
   B2= Y1[i+1] - Y1[1];
   area+= A1*B2 - A2*B1;
   }
if(area>0.0)
  area /= 2.0;
else
  area /= -2.0;

fprintf(fout,"%.2f\n",area);

fclose(fin);
fclose(fout);
return 0;
}