Cod sursa(job #2733774)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 30 martie 2021 21:19:18
Problema Poligon Scor 100
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 2.74 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("poligon.in");
ofstream fout("poligon.out");

const int NMAX(805), MMAX(60005);
int n, m, despZone[NMAX], nr;
double med;
bool vert;
struct punct
{
    int x, y;
} pnct[NMAX];
vector<int> DrepZone[NMAX];

double work(punct a, punct b)
{
    return a.y + (b.y - a.y) * (med - a.x) / ((double)b.x - a.x);
}

inline bool cmp(int a, int b)
{
    return work(pnct[a], pnct[a + 1]) < work(pnct[b], pnct[b + 1]);
}

void procesare()
{
    sort(despZone + 1, despZone + n + 1);
    despZone[0] = -1;
    for(int i = 1; i <= n; ++i)
        if(despZone[i] != despZone[nr])
            despZone[++nr] = despZone[i];

    pnct[n + 1] = pnct[1];
    despZone[nr + 1] = despZone[nr] + 1000;
    for(int i = 1; i <= nr; ++i)
    {
        for(int j = 1; j <= n; ++j)
            if((pnct[j].x <= despZone[i] && despZone[i + 1] <= pnct[j + 1].x) || (pnct[j + 1].x <= despZone[i] && despZone[i + 1] <= pnct[j].x))
                DrepZone[i].push_back(j);
        med = (double)(despZone[i] + despZone[i + 1]) / (double)2;
        sort(DrepZone[i].begin(), DrepZone[i].end(), cmp);
    }
}

long long det(punct a, punct b, punct c)
{
    return 1LL * a.x * b.y + 1LL * b.x * c.y + 1LL * c.x * a.y - 1LL * a.x * c.y - 1LL * b.x * a.y - 1LL * c.x * b.y;
}

inline bool comp(punct a, punct b)
{
    if(a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

inline bool ok(int i, int x, int y)
{
    long long d = 0;
    if(comp(pnct[i], pnct[i + 1]))
        d = det(pnct[i], pnct[i + 1], {x, y});
    else d = det(pnct[i + 1], pnct[i], {x, y});
    if(d == 0)
    {
        vert = 1;
        return 1;
    }
    return (d > 0);
}

int main()
{
    fin >> n >> m;

    for(int i = 1; i <= n; ++i)
    {
        fin >> pnct[i].x >> pnct[i].y;

        despZone[i] = pnct[i].x;
    }

    procesare();

    int rez = 0;
    for(int i = 1; i <= m; ++i)
    {
        int x, y;
        fin >> x >> y;

        int st = 1;
        int dr = nr;
        int best = 0;
        while(st <= dr)
        {
            int mij = (st + dr) / 2;
            if(despZone[mij] < x)
            {
                best = mij;
                st = mij + 1;
            }
            else dr = mij - 1;
        }

        st = vert = 0;
        int best2 = -1;
        dr = DrepZone[best].size() - 1;
        while(st <= dr)
        {
            int mij = (st + dr) / 2;
            if(ok(DrepZone[best][mij], x, y))
            {
                best2 = mij;
                st = mij + 1;
            }
            else dr = mij - 1;
        }
        ++best2;
        rez += ((best2 & 1) || vert);
    }
    fout << rez << '\n';
    return 0;
}