Cod sursa(job #1947792)

Utilizator Theodor1000Cristea Theodor Stefan Theodor1000 Data 31 martie 2017 12:53:27
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
#include <cstdio>
#include <algorithm>
#include <vector>

#define pii pair <int, int>
#define f first
#define s second

using namespace std;

int n, m;
pii v[1024], ban[1024], sor[1024];
vector <pii> segm[1024];
vector <int> ver[1024];

bool cmp (pii a, pii b)
{
    int ma = (v[a.f].s + v[a.s].s) / 2;
    int mb = (v[b.f].s + v[b.s].s) / 2;

    return ma < mb;
}

int det (pii a, pii b, pii c)
{
    long long rez = 1LL * (a.f - c.f) * (b.s - a.s) + (a.s - c.s) * (a.f - b.f);

    if (!rez) return 0;
    if (rez > 0LL) return 1;
    return -1;
}

int finb (int a)
{
    int st = 1, dr = n, poz = 0;
    for (; st <= dr;)
    {
        int mij = (st + dr) >> 1;
        if (ban[mij].f <= a && a <= ban[mij].s)
        {
            if (a == ban[mij].f) poz = mij, dr = mij - 1;
            else return mij;

            continue;
        }

        if (ban[mij].f > a) dr = mij - 1;
        else st = mij + 1;
    }

    return poz;
}

int fins (pii a, int i)
{
    int st = 0, dr = segm[i].size () - 1, poz = -1;
    for (; st <= dr;)
    {
        int mij = (st + dr) >> 1;
        int rez = det (a, v[segm[i][mij].f], v[segm[i][mij].s]);

        if (!rez) return -100;
        if (rez > 0) poz = mij, st = mij + 1;
        else dr = mij - 1;
    }

    return poz;
}

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 ("%d %d", &v[i].f, &v[i].s),
        sor[i] = v[i];

    v[n + 1] = v[1];
    v[0] = v[n];

    sort (sor + 1, sor + n + 1);

    int lst = 0;
    for (int in = 1; in < n; ++in)
    {
        if (sor[in].f == sor[in + 1].f) continue;

        int j = ++lst;
        ban[j] = {sor[in].f, sor[in + 1].f};

        for (int i = 1; i <= n; ++i)
        {
            if (min (v[i].f, v[i + 1].f) <= ban[j].f && ban[j].s <= max (v[i].f, v[i + 1].f))
            {
                if (v[i].f < v[i + 1].f) segm[j].push_back ({i, i + 1});
                else segm[j].push_back ({i + 1, i});
            }
        }

        sort (segm[j].begin (), segm[j].end (), cmp);

        for (int i = 0; i < segm[j].size (); ++i)
        {
            if (i > 0) ver[j].push_back (ver[j][i - 1]);
            else ver[j].push_back (0);

            ver[j][i] += (v[segm[j][i].f].f == v[segm[j][i].s].f);
        }
    }

    n = lst;
    int rez = 0;

    for (; m; --m)
    {
        int a, b;
        scanf ("%d %d", &a, &b);

        int i = finb (a);
        if (i < 1) continue;

        int j = fins (pii (a, b), i);

        if (j == -100)
        {
            ++rez;
            continue;
        }
        if (j < 0 || j >= segm[i].size ()) continue;

        if ((j + 1 - ver[i][j]) & 1) ++rez;
    }

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

    return 0;
}