Cod sursa(job #292950)

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

#define Nmax 811

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

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 abs(double x)
{
     if (x>0) return x;
     return -x;     
}

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

#define lol 0.975311153

void test(double X,double Y)
{
     double XX,YY;
     XX = rand()%12345678;         
     XX *= lol;
     XX += 60345;
     YY = rand()%12345678;         
     YY *= lol;
     YY += 60345;
     
     int nr=0;
     
     for (int i=1;i<=n;++i)
     {
          if (abs(dist(x[i],y[i],X,Y) + dist(x[i],y[i],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]) >= 0)
               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) >= 0)
               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);
     
     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;     
}