Cod sursa(job #3339860)

Utilizator Anul2024Anul2024 Anul2024 Data 10 februarie 2026 16:24:35
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.85 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin ("poligon.in");
ofstream fout ("poligon.out");
const int DIM = 801;
int n, m, q, x[DIM + 1];
struct pct
{
    double x, y;
};
pct v[DIM + 1];
vector <int> pt[DIM + 1];
struct segm
{
    pct p1, p2;
};
vector <segm> s[DIM + 1];
double det (pct a, pct b, pct c)
{
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool on_seg (pct a, pct b, pct p)
{
    if (det (a, b, p) != 0)
        return false;
    if (min (a.x, b.x) <= p.x && p.x <= max (a.x, b.x) && min (a.y, b.y) <= p.y && p.y <= max (a.y, b.y))
        return true;
    return false;
}
int get_x (double p)
{
    int l = 1, r = m, mid;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (x[mid] <= p)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return r;
}
bool cb (vector <segm> &v, pct p)
{
    int l = 0, r = (int) v.size () - 1, mid;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (det (v[mid].p1, v[mid].p2, p) > 0)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return (r + 1) % 2 || on_seg (v[r].p1, v[r].p2, p);
}
void read ()
{
    fin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        fin >> v[i].x >> v[i].y;
        x[i] = v[i].x;
    }
    v[n + 1] = v[1];
}
bool cmp (const segm &a, const segm &b)
{
    return (a.p1.y + a.p2.y) > (b.p1.y + b.p2.y);
}
double calc (pct a, pct b, double x)
{
    double p = (double) (b.y - a.y) * (x - a.x) / (b.x - a.x);
    p += a.y;
    return p;
}
void get_segm ()
{
    sort (x + 1, x + n + 1);
    m = 1;
    for (int i = 2; i <= n; i++)
    {
        if (x[i] != x[i - 1])
            x[++m] = x[i];
    }
    x[m + 1] = x[m];
    for (int pos = 1; pos < m; pos++)
    {
        int l = x[pos], r = x[pos + 1];
        for (int i = 1; i <= n; i++)
        {
            pct a = v[i], b = v[i + 1];
            if (a.x != b.x)
            {
                if (a.x == l)
                    pt[pos].push_back (a.y);
                else if (b.x == l)
                    pt[pos].push_back (b.y);
                if (a.x > b.x)
                    swap (a.x, b.x);
                if (a.x <= l && r <= b.x)
                    s[pos].push_back ({calc (a, b, l), calc (a, b, r)});
            }
        }
        sort (s[pos].begin (), s[pos].end (), cmp);
    }
}
void solve ()
{
    int sol = 0;
    pct p;
    while (q--)
    {
        fin >> p.x >> p.y;
        int pos = get_x (p.x);
        if (p.x == x[pos] && lower_bound (pt[pos].begin (), pt[pos].end (), p.y) == pt[pos].end ())
            sol++;
        else if (pos > 0 && pos <= m)
            sol += cb (s[pos], p);
    }
    fout << sol;
}
int main()
{
    read ();
    get_segm ();
    solve ();
    return 0;
}