Cod sursa(job #246789)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 21 ianuarie 2009 13:29:06
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <stdio.h>

int n,A[800],B[800],C[800],x[800],y[800];

int max(int x,int y)
{
 if (x<y) return y;
 return x;   
}
int min(int x,int y)
{
 if (x<y) return x;
 return y;
}

bool eq(int &x1,int &y1)
{
 for (int i=0;i<n;i++)
     if (A[i]*x1+B[i]*y1+C[i]==0) return 1;   
    return 0;
}

bool pol(int &x1,int &y1)
{
     int nr=0;
     for (int i=1;i<n;i++) 
     if (A[i]!=0)
     if (i<n-1) {
                int w = -C[i]-B[i]*y1;
                w = w/A[i];
                if (min(x[i],x[0])<=w && w<=max(x[i],x[0])) nr++;
                //if (min(y[i],y[0])<=y1 && y1<=max(y[i],y[0])) nr++;
                }
     else {
          int w = -C[i]-B[i]*y1;
          w = w/A[i];
          if (min(x[i],x[i-1])<=w && w<=max(x[i],x[i-1])) nr++;
          //if (min(y[i],y[i-1])<=y1 && y1<=max(y[i],y[i+1])) nr++;
          }
 //    printf("%d\n",nr);
     return (nr/2)%2;
}

int main()
{
 FILE *in = fopen("poligon.in","r");
 FILE *out = fopen("poligon.out","w");
 
 int m,i;
 fscanf(in,"%d%d",&n,&m);
 fscanf(in,"%d%d",&x[0],&y[0]);
  
  for (i=1;i<n;i++)
  {
      fscanf(in,"%d%d",&x[i],&y[i]);
      A[i-1] = y[i]-y[i-1];
      B[i-1] = x[i-1]-y[i];
      C[i-1] = x[i]*y[i-1]-x[i-1]*y[i];
      }
      A[n-1] = y[0]-y[n-1];
      B[n-1] = x[n-1]-y[0];
      C[n-1] = x[0]*y[n-1]-x[n-1]*y[0];  
  int x1,y1,nr=0;    
  for (;m;m--)
  {
  fscanf(in,"%d%d",&x1,&y1);    
  if (eq(x1,y1)) nr++;
  else if (pol(x1,y1)) nr++;     
  }
  fprintf(out,"%d\n",nr);scanf("\n");
}