Cod sursa(job #3168502)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 12 noiembrie 2023 16:43:43
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <bits/stdc++.h>
using namespace std;
int f[60001];
vector <int> points[60001];
vector <int> verticals;
vector <vector <int>> lines;
struct point{
    int x, y;
}v[801];
int n;

bool comp(int a, int b){
    double X = (1.0 * v[a].y + v[(a + 1) % n].y) / 2;
    double Y = (1.0 * v[b].y + v[(b + 1) % n].y) / 2;
    return X < Y;
}

int ishigher(int x, int y, int line){
    double Y = y;
    double _Y = 1.0 * v[line].y - 1.0 * (v[line].x - x) * (v[line].y - v[(line + 1) % n].y) / (v[line].x - v[(line + 1) % n].x);
    if(_Y == Y) return 0;
    if(_Y < Y) return 1;
    if(_Y > Y) return -1;
}

int main() {
    int m, i, j, x, y, pas;
    freopen("poligon.in", "r", stdin);
    freopen("poligon.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(i = 0; i < n; i++) {
        scanf("%d%d", &v[i].x, &v[i].y);
        f[v[i].x] = 1;
        points[v[i].x].push_back(v[i].y);
    }
    for(i = 0; i <= 60000; i++) {
        if(f[i]) {
            verticals.push_back(i);
            sort(points[i].begin(), points[i].end());
        }
    }
    for(i = 1; i < verticals.size(); i++){
        vector <int> aux;
        for(j = 0; j < n; j++)
            if(min(v[j].x, v[(j + 1) % n].x) <= verticals[i - 1] && max(v[j].x, v[(j + 1) % n].x) >= verticals[i] && v[j].x != v[(j + 1) % n].x)
                aux.push_back(j);
        lines.push_back(aux);
    }
    for(int k = 0; k < lines.size(); k++){
        sort(lines[k].begin(), lines[k].end(), comp);
    }
    int sol = 0;
    while(m--){
        scanf("%d%d", &x, &y);
        pas = 1 << 16;
        i = 0;
        while(pas){
            if(i + pas < verticals.size() && verticals[i + pas] <= x)
                i += pas;
            pas >>= 1;
        }
        if(verticals[i] == x){
            j = 0;
            pas = 1 << 9;
            while(pas){
                if(j + pas < points[x].size() && points[x][j + pas] <= y)
                    j += pas;
                pas /= 2;
            }
            if(j % 2 == 0)
                sol++;
        }
        else{
            j = 0;
            pas = 1 << 9;
            while(pas) {
                if (j + pas < lines[i].size() && ishigher(x, y, lines[i][j + pas]) > 0) {
                    j += pas;
                }
                pas >>= 1;
            }
            if(ishigher(x, y, lines[i][j]) == 0){
                sol++;
            }
            else
                if(j % 2 == 0)
                    sol++;
        }
    }
    printf("%d\n", sol);

    return 0;
}