Cod sursa(job #3343076)

Utilizator Anul2024Anul2024 Anul2024 Data 26 februarie 2026 14:12:34
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.71 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#define double long double
using namespace std;
ifstream fin ("poligon.in");
ofstream fout ("poligon.out");
const int DIM = 801;
const double EPS = 1e-6;
int n, m, q, x[DIM + 1];
struct pct
{
    double x, y;
};
pct v[DIM + 1];
vector <pct> pt[DIM + 1];
struct segm
{
    pct p1, p2;
};
vector <segm> s[DIM + 1];
double sgn (double val)
{
    if (abs (val) < EPS)
        return 0;
    return (val > 0 ? 1 : 0);
}
double det (pct a, pct b, pct c)
{
    return sgn ((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;
}
bool cmp2 (const pct &a, const pct &b)
{
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}
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 || (a.x == b.x && a.y > b.y))
                swap (a, b);
            if (a.x != b.x)
            {
                if (a.x == l)
                    pt[pos].push_back ({a.y, a.y});
                else if (b.x == l)
                    pt[pos].push_back ({b.y, b.y});
                if (a.x <= l && r <= b.x)
                {
                    segm ss = { {(double) l, calc (a, b, l)}, {(double) r, calc (a, b, r)} };
                    s[pos].push_back (ss);
                }
            }
            else if (a.x == l)
                pt[pos].push_back ({a.y, b.y});
        }
        sort (s[pos].begin (), s[pos].end (), cmp);
        sort (pt[pos].begin (), pt[pos].end (), cmp2);
    }
}
bool cb_pt (vector <pct> &s, double y)
{
    int l = 0, r = (int) s.size () - 1, mid;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (s[mid].x <= y)
            l = mid + 1;
        else
            r = mid - 1;
    }
    if (r >= 0 && s[r].y >= y)
        return true;
    return false;
}
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])
        {
            if (cb_pt (pt[pos], p.y))
                sol++;
        }
        else if (pos > 0 && pos <= m)
            sol += cb (s[pos], p);
    }
    fout << sol;
}
int main()
{
    read ();
    get_segm ();
    solve ();
    return 0;
}