Cod sursa(job #40497)

Utilizator alecmanAchim Ioan Alexandru alecman Data 27 martie 2007 14:27:09
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
/*
 *
 *
  info-arena 2.0 - Arhiva - Poligon
 *
 *
 */

#include<stdio.h>

#define INPUT "poligon.in"
#define OUTPUT "poligon.out"

FILE *fin=fopen(INPUT, "r"),*fout=fopen(OUTPUT, "w");

int n;
long m,a[802][2],x,y;

void citire();
int rezolva();

int main()
{
  citire();
  long total=0;
  for(long i=1;i<=m;++i)
  {
    fscanf(fin, "%ld %ld", &x, &y);
    if(rezolva())
      ++total;
  }
  fprintf(fout, "%ld\n", total);
  fclose(fin);
  fclose(fout);
  return 0;
}

void citire()
{
  fscanf(fin, "%d %ld", &n, &m);
  for(int i=1;i<=n;++i)
    fscanf(fin, "%ld %ld", &a[i][0],&a[i][1]);
  a[n+1][0]=a[1][0];
  a[n+1][1]=a[1][1];
}

int rezolva()
{
  long stanga=0,dreapta=0;
  double pozx=0.0;
  for(int i=1;i<=n;++i)
  {
    if((a[i][1]<=y&a[i+1][1]>=y)||(a[i][1]>=y&&a[i+1][1]<=y))
    {
      if(y==a[i][1]&&y==a[i+1][1])
      {
        if(a[i][0]<x&&a[i+1][0]<x)
          ++stanga;
        else
        if(a[i][0]>x&&a[i+1][0]>x)
          ++dreapta;
      }
      else
      {
        pozx=(double)(((a[i][0]-a[i+1][0])*y+(a[i+1][0]*a[i][1]-a[i][0]*a[i+1][1]))/(a[i][1]-a[i+1][1]));
        if(pozx<x)
          ++stanga;
        else
        if(pozx>x)
          ++dreapta;
      }
    }
  }
  if(stanga%2!=0||dreapta%2!=0)
    return 1;
  return 0;
}