Cod sursa(job #53973)

Utilizator moga_florianFlorian MOGA moga_florian Data 23 aprilie 2007 21:04:57
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include<stdio.h>
#define Nmax 804

int x[Nmax],y[Nmax],A[Nmax],B[Nmax],C[Nmax];

int main()
{
FILE *fin=fopen("poligon.in","r"),
     *fout=fopen("poligon.out","w");
     
int N,M,i,j,X,Y;   
fscanf(fin,"%d%d",&N,&M);

for(i=1;i<=N;i++)
  {
  fscanf(fin,"%d%d",&x[i],&y[i]);
  if(x[i]>30000 || y[i]>30000)
      for(;;);
  }
  
x[N+1]=x[1];
y[N+1]=y[1];

for(i=1;i<=N;i++)
  {
  A[i]= y[i+1]-y[i];
  B[i]= x[i] - x[i+1];              
  C[i]= y[i]* (x[i+1]-x[i]) - x[i]* (y[i+1]-y[i]);
  }
  
double y0;
int nr,sol=0,stx,drx,sty,dry,ok,gasit;

for(i=1;i<=M;i++)
  {
  fscanf(fin,"%d%d",&X,&Y);       
  if(X>30000 || Y>30000)
     for(;;);
  nr=0;
  
  gasit=0;
  for(j=1;j<=N;j++)
     if(A[j]*X+B[j]*Y+C[j] == 0)
        {
        ok=1;
        gasit=1;                  
        if(x[j] < x[j+1])
          {
          if( x[j]<=X && X<x[j+1] );
          else ok=0;
          }
        else
          {
          if( x[j]>=X && X>x[j+1] );
          else ok=0;             
          } 
       
       if(y[j] < y[j+1])
          {
          if( y[j] <= Y && Y < y[j+1] );
          else ok=0;
          }
        else
          {        
          if( y[j] >= Y && Y > y[j+1] );
          else ok=0;
          } 
          
        if(ok)
          sol++;
        }
          
  if(gasit);
  else
  {
  for(j=1;j<=N;j++)
     {
     y0= ((double)(-C[j]-A[j]*X)) / (double)B[j];
     
     ok=1;
     
     if(x[j] < x[j+1])
       {
       if( x[j]<=X && X<x[j+1] );
       else ok=0;
       }
     else
       {
       if( x[j]>=X && X>x[j+1] );
       else ok=0;             
       } 
       
     if(y[j] < y[j+1])
       {
       if( (double)y[j] <= y0 && y0 < (double)y[j+1] );
       else ok=0;
       }
     else
       {        
       if( (double)y[j] >= y0 && y0 > (double)y[j+1] );
       else ok=0;
       } 
       
     if( ok && y0< (double)Y)
          nr++;
     }  
     
  if(nr%2)
     sol++;
  }     
  }
    
fprintf(fout,"%d\n",sol);
fclose(fin);
fclose(fout);
return 0;    
}