Cod sursa(job #53958)

Utilizator moga_florianFlorian MOGA moga_florian Data 23 aprilie 2007 20:36:57
Problema Poligon Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 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]);
  
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;

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