Cod sursa(job #3155217)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 7 octombrie 2023 18:04:22
Problema Poligon Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int max_size = 6e2 + 1, max_v = 6e4;

pair <double, double> pct[max_size];
int benzi[max_size], coincide;
double med;
vector <int> inq[max_size];

double calc_y (int x)
{
    return (double)(pct[x].second + (double)(pct[x + 1].second - pct[x].second) / (pct[x + 1].first - pct[x].first) * (med - pct[x].first));
}

bool cmp (int x, int y)
{
    return calc_y(x) < calc_y(y);
}

int arie (pair <double, double> x, pair <double, double> y, pair <double, double> z)
{
    return x.first * (y.second - z.second) + y.first * (z.second - x.second) + z.first * (x.second - y.second);
}

bool check (int x, int y, int z)
{
    int s;
    if (pct[z] < pct[z + 1])
    {
        s = arie(pct[z], pct[z + 1], {x, y});
    }
    else
    {
        s = arie(pct[z + 1], pct[z], {x, y});
    }
    if (s == 0)
    {
        coincide = 1;
    }
    return (s >= 0);
}

int main ()
{
    int n, q;
    in >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        in >> pct[i].first >> pct[i].second;
        benzi[i] = pct[i].first;
    }
    pct[n + 1] = pct[1];
    sort(benzi + 1, benzi + n + 1);
    benzi[0] = -1;
    int m = 0;
    for (int i = 1; i <= n; i++)
    {
        if (benzi[m] != benzi[i])
        {
            benzi[++m] = benzi[i];
        }
    }
    benzi[m + 1] = benzi[m] + max_v;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if ((pct[j].first <= benzi[i] && benzi[i + 1] <= pct[j + 1].first) || (pct[j + 1].first <= benzi[i] && benzi[i + 1] <= pct[j].first))
            {
                inq[i].push_back(j);
            }
        }
        med = (double)(benzi[i] + benzi[i + 1]) / 2;
        sort(inq[i].begin(), inq[i].end(), cmp);
    }
    int ans = 0;
    while (q--)
    {
        int x, y;
        in >> x >> y;
        coincide = 0;
        int poz1 = 0, e = 20;
        while (e >= 0)
        {
            if (poz1 + (1 << e) <= m && benzi[poz1 + (1 << e)] < x)
            {
                poz1 += (1 << e);
            }
            e--;
        }
        int poz2 = -1;
        e = 20;
        while (e >= 0)
        {
            if (poz2 + (1 << e) < inq[poz1].size() && check(x, y, inq[poz1][poz2 + (1 << e)]))
            {
                poz2 += (1 << e);
            }
            e--;
        }
        poz2++;
        if (poz2 % 2 == 1 || coincide == 1)
        {
            ans++;
        }
    }
    out << ans;
    in.close();
    out.close();
    return 0;
}
/*
4 3
0 0
0 100
100 100
100 0
50 50
100 50
100 110
*/