Cod sursa(job #1346699)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 18 februarie 2015 15:51:22
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <cstdio>
#include <algorithm>

#define punct pair < int , int >

#define eps 1e-12

#define x first
#define ST first
#define y second
#define DR second

#define Nmax 800 + 10
#define Vmax 60000 + 10

using namespace std;

int n , m , i , j , st , dr , nrF , xx , yy , sol;
int a1 , b1 , c1 , a2 , b2 , c2;

int sX[Vmax] , L[Nmax];

double S[Nmax][Nmax];

double Y[Nmax];

punct a[Nmax] , f[Nmax];


void ecuatia_dreptei(punct A , punct B , int &a , int &b , int &c)
{
    a = A.y - B.y;
    b = B.x - A.x;
    c = A.x * B.y - B.x * A.y;
}

void cb(int x1 , int x2 , int &st , int &dr)
{
    st = 1; dr = nrF;

    for (int mij = (st + dr) >> 1; st <= dr; mij = (st + dr) >> 1)
    {
        if (f[mij].DR < x1) st = mij + 1;
        else dr = mij - 1;
    }

    int aux1 = st;

    st = 1; dr = nrF;

    for (int mij = (st + dr) >> 1; st <= dr; mij = (st + dr) >> 1)
    {
        if (f[mij].ST > x2) dr = mij - 1;
        else st = mij + 1;
    }

    dr = dr; st = aux1;
}

int cb2(int poz , int yy)
{
    int st = 1; int dr = L[poz];

    for (int mij = (st + dr) >> 1; st <= dr; mij = (st + dr) >> 1)
    {
        if (S[poz][mij] > yy + eps) dr = mij - 1;
        else st = mij + 1;
    }

    return dr;
}

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

    scanf("%d %d", &n , &m);

    for (i = 1; i <= n; ++i)
    {
        scanf("%d %d", &a[i].x , &a[i].y);
        sX[a[i].x] = true;
    }


    st = dr = -1;

    for (i = 0; i <= 60000; ++i)
    {
        if (st == -1 && sX[i]) st = i;
        else if (st > -1 && dr == -1 && sX[i]) dr = i;

        if (st != -1 && dr != -1)
         f[++nrF].ST = st , f[nrF].DR = dr , st = dr , dr = -1;
    }

    f[++nrF].ST = st; f[nrF].DR = f[1].ST;

    a[++n].x = a[1].x; a[++n].y = a[1].y;

    for (i = 1; i < n; ++i)
    {
        ecuatia_dreptei(a[i] , a[i+1] , a1 , b1 , c1);
        cb(a[i].x , a[i+1].x , st , dr);

        int lg = 0;

        for ( j = st; j <= dr; ++j)
        {
            ecuatia_dreptei(make_pair(f[j].ST , -1) , make_pair(f[j].ST ,  60001) , a2 , b2 , c2);
            if (a1 * b2 == a2 * b1);
            else Y[++lg] = (1.0 * (c1 * a2 - c2 * a1)) /  (1.0 * (b2 * a1 - b1 * a2));
        }

        for (j = 1; j <= lg; ++j)
            if (Y[j] + eps < Y[j+1]) S[st+j-1][++L[st+j-1]] = Y[j];
            else S[st+j-1][++L[st+j-1]] = Y[j+1];
    }

    for (i = 1; i < nrF; ++i)
     sort(S[i] + 1 , S[i] + L[i] + 1);

    for (i = 1; i <= m; ++i)
    {
        scanf("%d %d", &xx , &yy);
        cb(xx , yy , st , dr);
        if (cb2(st , yy) % 2) sol++;
    }

    printf("%d\n", sol);

    return 0;
}