Cod sursa(job #3157470)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 15 octombrie 2023 16:41:57
Problema Poligon Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;

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

const int DELTA = 6e4;
const int MAX = 2100;

typedef pair<double, double> Point;

Point point[MAX];
vector<int> functii[MAX];
int benzi[MAX], good;
double med;
int n, q;
int ans;

static inline double calc_y(const int& x) {
    return (double)(point[x].second + (double)(point[x + 1].second - point[x].second) / (point[x + 1].first - point[x].first) * (med - point[x].first));
}

static inline int arie(const Point& x, const Point& y, const Point& z) {
    return x.first * (y.second - z.second) + y.first * (z.second - x.second) + z.first * (x.second - y.second);
}

static inline bool check(int x, int y, int z) {
    int s;
    if(point[z].first < point[z + 1].first || (point[z].first == point[z + 1].first && point[z].second < point[z + 1].second))
        s = arie(point[z], point[z + 1], {x, y});
    else s = arie(point[z + 1], point[z], {x, y});
    
    if(s == 0)
        good = 1;

    return (s >= 0);
}

int main()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> point[i].first >> point[i].second;
        benzi[i] = point[i].first;
    }
    point[n + 1] = point[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] + DELTA;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++)
            if ((point[j].first <= benzi[i] && benzi[i + 1] <= point[j + 1].first) || (point[j + 1].first <= benzi[i] && benzi[i + 1] <= point[j].first))
                functii[i].push_back(j);
        
        med = (double)(benzi[i] + benzi[i + 1]) / 2;
        sort(functii[i].begin(), functii[i].end(), [](const int& A, const int& B) {
                return calc_y(A) < calc_y(B);
            } );
    }

    int x, y;
    while(q--) {
        cin >> x >> y;

        good = 0;
        int banda = 0;
        for(int pas = 20; pas >= 0; pas--)
            if(banda + (1 << pas) <= m && benzi[banda + (1 << pas)] < x)
                banda += (1 << pas);
            
        int intersecti = -1;
        for(int pas = 20; pas >= 0; pas--)
            if(intersecti + (1 << pas) < functii[banda].size() && check(x, y, functii[banda][intersecti + (1 << pas)]))
                intersecti += (1 << pas);
            
        ans += !(intersecti & 1) + (good * (intersecti & 1));
    }

    cout << ans << '\n';
    return 0;
}