Cod sursa(job #2914860)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 21 iulie 2022 10:04:32
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
/// Preset de infoarena
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int maxN = 805;
int n, q, a[maxN], ans;
double med;
bool vert;
vector <int> v[maxN];

struct point
{
    int cx, cy;
} pct[maxN];

double calc(point x, point y, double med)
{
    return x.cy + 1.0 * (y.cy - x.cy) * (med - x.cx) / (y.cx - x.cx);
}
bool cmp(int x, int y)
{
    return (calc(pct[x], pct[x + 1], med) < calc(pct[y], pct[y + 1], med));
}

int arie(point a, point b, point c)
{
    /// ax ay 1 )
    /// bx by 1  ) => d = ax * by + ay * cx + bx * cy - by * cx - ay * bx - ax * cy
    /// cx cy 1 )
    return a.cx * b.cy + a.cy * c.cx + b.cx * c.cy - b.cy * c.cx - a.cy * b.cx - a.cx * c.cy;
}
bool check(int x, point p)
{
    int S = 0;
    if(pct[x].cx < pct[x + 1].cx || (pct[x].cx == pct[x + 1].cx && pct[x].cy < pct[x + 1].cy))
        S = arie(pct[x], pct[x + 1], p);
    else
        S = arie(pct[x + 1], pct[x], p);
    if(S == 0)
        vert = 1;
    return (S >= 0);
}

int main()
{
    fin >> n >> q;
    for(int i = 1; i <= n; i++)
    {
        fin >> pct[i].cx >> pct[i].cy;
        a[i] = pct[i].cx;
    }
    pct[n + 1] = pct[1];
    sort(a + 1, a + n + 1);
    a[0] = -1;
    int k = 0;
    for(int i = 1; i <= n; i++)
        if(a[i] != a[k])
            a[++k] = a[i];
    a[k + 1] = a[k] + 1000;
    for(int i = 1; i <= k; i++)
    {
        for(int j = 1; j <= n; j++)
            if((pct[j].cx <= a[i] && a[i + 1] <= pct[j + 1].cx) || (pct[j + 1].cx <= a[i] && a[i + 1] <= pct[j].cx))
                v[i].push_back(j);
        med = (double)(a[i] + a[i + 1]) / 2;
        sort(v[i].begin(), v[i].end(), cmp);
    }
    for(int i = 1; i <= q; i++)
    {
        point p;
        fin >> p.cx >> p.cy;
        int poz = 0, aux = 0;
        for(int i = (1 << 10); i > 0; i >>= 1)
            if(poz + i <= k && a[poz + i] < p.cx)
                poz += i;
        vert = 0;
        for(int i = (1 << 10); i > 0; i >>= 1)
            if(aux + i < v[poz].size() && check(v[poz][aux + i], p))
                aux += i;
        if(aux % 2 == 0 || vert)
            ans++;
    }
    fout << ans << '\n';
    return 0;
}