Cod sursa(job #3319591)

Utilizator unomMirel Costel unom Data 1 noiembrie 2025 22:41:23
Problema Poligon Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.61 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

#define int long long

ifstream in("poligon.in");
ofstream out("poligon.out");
int n, m, ans;
pair<int, int> v[805];

int det(int x1, int y1, int x2, int y2, int x3, int y3)
{
    return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
}

int pctseg(int x1, int y1, int x2, int y2, int x3, int y3)
{
    int d = det(x1, y1, x2, y2, x3, y3);

    if(d == 0 && x3 >= min(x1, x2) && x3 <= max(x1, x2) && y3 >= min(y1, y2) && y3 <= max(y1, y2))
    {
        return 1;
    }

    return 0;
}

struct Edge {
    int x1,y1,x2,y2;
    int dx,dy;
    int ymin,ymax;
};

signed main()
{
    in>>n>>m;

    for(int i = 1; i<=n; i++)
    {
        in>>v[i].first>>v[i].second;
    }

    vector<Edge> edges;
    edges.reserve(n);
    for(int i = 1; i <= n; ++i)
    {
        int j = (i==n?1:i+1);
        Edge e;
        e.x1 = v[i].first; e.y1 = v[i].second;
        e.x2 = v[j].first; e.y2 = v[j].second;
        e.dx = e.x2 - e.x1;
        e.dy = e.y2 - e.y1;
        e.ymin = min(e.y1, e.y2);
        e.ymax = max(e.y1, e.y2);
        edges.push_back(e);
    }

    const int YMAX = 60000;
    const int BLOCK = 128;
    int nblocks = (YMAX / BLOCK) + 3;
    vector<vector<int>> bucket(nblocks);
    vector<vector<int>> horiz(YMAX + 1);

    for(int id = 0; id < (int)edges.size(); ++id)
    {
        Edge &e = edges[id];
        if(e.ymin == e.ymax)
        {
            if(e.ymin >= 0 && e.ymin <= YMAX)
            {
                horiz[e.ymin].push_back(id);
            }
            continue;
        }
        int b1 = e.ymin / BLOCK;
        int b2 = (e.ymax - 1) / BLOCK;
        if(b1 < 0)
        {
            b1 = 0;
        }
        if(b2 >= nblocks)
        {
            b2 = nblocks - 1;
        }
        for(int b = b1; b <= b2; ++b)
        {
            bucket[b].push_back(id);
        }
    }

    ans = 0;
    while(m--)
    {
        int px, py;
        in>>px>>py;

        bool onEdge = false;
        int crosses = 0;

        if(py >= 0 && py <= YMAX)
        {
            for(int id : horiz[py])
            {
                Edge &e = edges[id];
                if(px >= min(e.x1, e.x2) && px <= max(e.x1, e.x2))
                {
                    onEdge = true;
                    break;
                }
            }
            if(onEdge)
            {
                ans++;
                continue;
            }
        }

        int b = py / BLOCK;
        if(b < 0)
        {
            b = 0;
        }
        if(b >= nblocks)
        {
            b = nblocks - 1;
        }
        const vector<int> &vec = bucket[b];
        for(int id : vec)
        {
            Edge &e = edges[id];
            if(!(e.ymin <= py && py < e.ymax))
            {
                continue;
            }
            if(pctseg(e.x1, e.y1, e.x2, e.y2, px, py))
            {
                onEdge = true;
                break;
            }
            int left = (px - e.x1) * e.dy;
            int right = e.dx * (py - e.y1);
            if(e.dy > 0)
            {
                if(left < right)
                {
                    crosses++;
                }
            }
            else
            {
                if(left > right)
                {
                    crosses++;
                }
            }
        }

        if(onEdge)
        {
            ans++;
        }
        else if(crosses % 2 == 1)
        {
            ans++;
        }
    }

    out<<ans;

    return 0;
}