Cod sursa(job #1347543)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 19 februarie 2015 00:29:24
Problema Poligon Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.18 kb
#include <cstdio>
#include <algorithm>

#define punct pair < double , double >

#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 , nrF , sol , st , dr , cop , xx , yy , v;

double a1 , b1 , c1 , a2 , b2 , c2;

int sX[Vmax] , L[Nmax];

punct S[Nmax][Nmax];

double Y[Nmax];

pair < int , int > a[Nmax] , f[Nmax] , vert[Vmax];


void ecuatia_dreptei(punct A , punct B , double &a , double &b , double &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].ST < 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].DR > x2) dr = mij - 1;
        else st = mij + 1;
    }

    dr = dr; st = aux1;
}

bool cb2(int poz , int yy)
{
    double Y; int crt;

    int st = 1; int dr = L[poz];

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

    crt = dr;

    dr++;

    while (dr <= L[poz] && (S[poz][dr].first + eps < yy || S[poz][dr].second + eps < yy))
    {
        ecuatia_dreptei(make_pair(1.0 * f[poz].ST , S[poz][dr].first) , make_pair(1.0 * f[poz].DR , S[poz][dr].second) , a2 , b2 , c2);

        if (a1 * b2 - a2 * b1 <= eps && a1 * b2 - a2 * b1 >= 0) Y = 60002;
        else Y = (c1 * a2 - c2 * a1) /  (b2 * a1 - b1 * a2);

        if (Y + eps < yy * 1.0) crt++;
        else if (Y - 1.0 * yy <= eps) return true;

        dr++;
    }

    return (crt % 2 == 1);
}

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

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

    for (i = 0 ; i <= 60000; ++i)
     vert[i].ST = 60002 , vert[i].DR = -1;

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

        if (a[i].x == a[i-1].x)
        vert[a[i].x].ST = min(vert[a[i].x].ST , min(a[i-1].y , a[i].y)) , vert[a[i].x].DR = max(vert[a[i].x].DR , max(a[i].y,a[i-1].y));
    }

    st = dr = -1;

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

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

    a[++n].x = a[1].x; a[n].y = a[1].y;
    f[nrF+1] = f[1]; f[0].DR = f[1].ST;

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

        int lg = 0;

        for ( j = min(st , dr); j <= max(st , dr); ++j)
        {
            ecuatia_dreptei(make_pair(1.0 * f[j].ST , -1.0) , make_pair(f[j].ST * 1.0 ,  60001.0) , a2 , b2 , c2);
            if (a1 * b2 - a2 * b1 <= eps && a1 * b2 - a2 * b1 >= 0);
            else Y[++lg] = (c1 * a2 - c2 * a1) /  (b2 * a1 - b1 * a2);
        }
        Y[++lg] = cop;

        for (j = 1; j < lg; ++j)
            S[st+j-1][++L[st+j-1]] = make_pair(Y[j],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);
        ecuatia_dreptei(make_pair(xx * 1.0 , -1.0), make_pair(xx * 1.0 , 60001.0) , a1 , b1 , c1);

        if (yy >= vert[xx].ST && yy <= vert[xx].DR)
        {
            sol++;
            continue;
        }

        cb(xx , yy , st , dr);

        if (st == nrF + 1 && xx <= f[nrF].DR) st--;
        else if (st <= nrF) st--;

        if (cb2(st , yy)) sol++;
    }

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

    return 0;
}