Cod sursa(job #3175929)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 26 noiembrie 2023 15:54:26
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <bits/stdc++.h>
#define EPS 0.000001
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;
double MED;
bool comp(int a, int b){
    double K1 = (1.0 * (v[a].y - v[(a + 1) % n].y) / (1.0 * v[a].x - v[(a + 1) % n].x)) * (1.0 * MED - v[a].x) + v[a].y;
    double K2 = (1.0 * (v[b].y - v[(b + 1) % n].y) / (1.0 * v[b].x - v[(b + 1) % n].x)) * (1.0 * MED - v[b].x) + v[b].y;
    return K1 < K2;
}

int ishigher(double x, double 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 || (x - v[line].x) * (v[line].y - v[(line + 1) % n].y) == (y - v[line].y) * (v[line].x - v[(line + 1) % n].x)) return 0;
    if(_Y < Y) return 1;
    if(_Y > Y) return -1;
}
int sol = 0;

bool check(int i, double x, double y){
    int j, pas;
    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++;
}
int main() {
    int m, i, j, 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++){
        MED = (1.0 * verticals[k] + verticals[k + 1]) / 2.0;
        sort(lines[k].begin(), lines[k].end(), comp);
    }

    while(m--){
        double x, y;
        scanf("%lf%lf", &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){
           if(i != verticals.size() - 1) {
               x += EPS;
               check(i, x, y);
           }
           x -= 2 * EPS;
           check(i - 1, x, y);
        }
        else{
            check(i,x ,y);
        }
    }
    printf("%d\n", sol);

    return 0;
}