Cod sursa(job #842988)

Utilizator stoicatheoFlirk Navok stoicatheo Data 27 decembrie 2012 12:43:59
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
 
 
#define PII pair<int, int>
#define pb push_back
#define x first
#define y second
#define nmax 810
 
PII A[nmax], crtP;
int B[nmax], C[nmax], X[nmax], Y[nmax], Z[nmax], N, M, ans, ok, left, right, step;
double XX[nmax], ZZ[nmax];
vector<int> Banda[nmax];
 
 
bool cmp(int ind1, int ind2)
{
     return (XX[ind1] * (left + right) + 2 * ZZ[ind1] < XX[ind2] * (left + right) + 2 * ZZ[ind2]);
}
 
bool Check(int ind, PII P)
{
     if(X[ind] * P.x + Y[ind] * P.y + Z[ind] == 0) ok = 1;
     return (P.y >= XX[ind] * P.x + ZZ[ind]);
}
 
int main()
{
    freopen("poligon.in", "r", stdin);
    freopen("poligon.out", "w", stdout);
    int i, j;
    scanf("%i %i", &N, &M);
    for(i = 1; i <= N; i++)
          scanf("%i %i", &A[i].x, &A[i].y);
    A[N + 1] = A[1];
    for(i = 1; i <= N; i++)
    {
          X[i] = (A[i + 1].y - A[i].y);
          Y[i] = (A[i].x - A[i + 1].x);
          Z[i] = (A[i].y * A[i + 1].x - A[i].x * A[i + 1].y);
          XX[i] = -1.0 * X[i] / Y[i];
          ZZ[i] = -1.0 * Z[i] / Y[i];
    }
    for(i = 1; i <= N; i++)
          B[i] = A[i].x;
    sort(B + 1, B + N + 1);
    C[++C[0]] = B[1];
    for(i = 2; i <= N; i++)
          if(B[i] != B[i - 1])
                  C[++C[0]] = B[i];
    for(i = 1; i <= C[0]; i++)
    {
          for(j = 1; j <= N; j++)
                if(min(A[j].x, A[j + 1].x) <= C[i] && C[i] < max(A[j].x, A[j + 1].x))
                               Banda[i].pb(j);
          left = C[i], right = C[i + 1];
          sort(Banda[i].begin(), Banda[i].end(), cmp);
    }
    for(; M; M --)
    {
          scanf("%i %i", &crtP.x, &crtP.y);
          if(C[1] <= crtP.x && crtP.x <= C[C[0]])
          {
                  ok = 0;
                  step = 1024, i = 0, j = 0;
                  for(; step; step /= 2)
                        if(i + step <= C[0] && C[i + step] < crtP.x)
                             i += step;
    
                  for(step = 1024; step; step /= 2)
                        if(j + step <= Banda[i].size() && Check(Banda[i][j + step - 1], crtP))
                             j += step;
               
                  ans = ans + max(j % 2, ok);
          }
    }
    printf("%i\n", ans);
    return 0;
}