Cod sursa(job #292964)

Utilizator crawlerPuni Andrei Paul crawler Data 31 martie 2009 20:43:43
Problema Poligon Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <stdio.h>
#include <math.h>

#define Nmax 811

double x[Nmax], y[Nmax];
int n,m,ret;
double XX,YY;

int sens(double x3,double y3,double x1,double y1,double x2,double y2)
{
     x1 -= x3;
     y1 -= y3;
     x2 -= x3;
     y2 -= y3;
     double tmp = x1*y2-x2*y1;
     if (tmp < 0)
          return -1;
     if (tmp > 0)
          return 1;
     return 0;
}

double abs1(double x)
{
     if (x>0) return x;
     return -x;     
}

double dist(double x1,double y1,double x2,double y2)
{
     x1 -= x2;
     y1 -= y2;
     return x1*x1+y1*y1;     
}

#define lol 0.975311153

void test(double X,double Y)
{
     
     int nr=0;
     
     for (int i=1;i<=n;++i)
     {
          if (abs1(dist(x[i],y[i],X,Y) + dist(x[i-1],y[i-1],X,Y) - dist(x[i],y[i],x[i-1],y[i-1])) < 1e-15)
          {
               ++ret;
               return;     
          }     
          
          int ok = 1;
          if (sens(X,Y,XX,YY,x[i],y[i])==sens(X,Y,XX,YY,x[i-1],y[i-1]))
               ok = 0;
          if (sens(x[i-1],y[i-1],x[i],y[i],X,Y)==sens(x[i-1],y[i-1],x[i],y[i],XX,YY))
               ok = 0;
          if (ok)
               ++nr;
     }
     if (nr%2 == 1)
          ++ret;
    // printf("%.0f %.0f\n", X,Y);
}

int main()
{
     freopen("poligon.in","r",stdin);
     freopen("poligon.out","w",stdout);
 

     XX = 60666.12345671;
     YY = 61111.67885431;
     
     scanf("%d%d", &n, &m);
     
     for (int i=1;i<=n;++i)
          scanf("%lf%lf", &x[i], &y[i]);
          
     x[0] = x[n];
     y[0] = y[n];
     
     double xx,yy;
     
     while (m--)
     {
          scanf("%lf%lf", &xx, &yy);
          test(xx,yy);
     }
     
     printf("%d\n", ret);
     
     
     
     return 0;     
}