Cod sursa(job #1288542)

Utilizator dariusdariusMarian Darius dariusdarius Data 8 decembrie 2014 21:33:27
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.14 kb
#include <cmath>

#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 805;
const int MAX_X = 60005;

vector< pair<int, int> > v[MAX_X];
struct Point {
    int x, y;
} a[MAX_N];
double pos;
vector<int> place[MAX_N];

inline double get_y(int i, double pos) {
    return a[i].y + 1.0 * (a[i + 1].y - a[i].y) * (pos - a[i].x) / (a[i + 1].x - a[i].x);
}

inline bool cmp(const int &a, const int &b) {
    return get_y(a, pos) < get_y(b, pos);
}

inline bool exists(const vector< pair<int, int> > &v, int y) {
    int left = 0, right = v.size() - 1, last = v.size() - 1;
    while (left <= right) {
        int middle = (left + right) / 2;
        if (v[middle].second >= y) {
            last = middle;
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
    return v[last].first <= y && y <= v[last].second;
}

int main() {
    ifstream fin("poligon.in");
    ofstream fout("poligon.out");
    int n, q;
    fin >> n >> q;
    vector<int> lines;
    for (int i = 1; i <= n; ++ i) {
        fin >> a[i].x >> a[i].y;
        lines.push_back(a[i].x);
    }
    sort(lines.begin(), lines.end());
    lines.erase(unique(lines.begin(), lines.end()), lines.end());
    int m = lines.size() - 1; ///number of regions
    a[0].x = a[n].x; a[0].y = a[n].y;
    for (int i = 0; i < n; ++ i) {
        if (a[i].x == a[i + 1].x) {
            v[a[i].x].push_back(make_pair(min(a[i].y, a[i + 1].y), max(a[i].y, a[i + 1].y)));
        } else {
            for (int j = 0; j < m; ++ j) {
                if (min(a[i].x, a[i + 1].x) <= lines[j] && lines[j + 1] <= max(a[i].x, a[i + 1].x)) {
                    place[j].push_back(i);
                }
            }
        }
    }
    for (int i = 0; i < m; ++ i) {
        pos = (lines[i] + lines[i + 1]) * 0.5;
        sort(place[i].begin(), place[i].end(), cmp);
    }
    for (int i = 0; i < MAX_X; ++ i) {
        sort(v[i].begin(), v[i].end());
    }
    int count = 0;
    for (int i = 1; i <= q; ++ i) {
        int x, y;
        fin >> x >> y;
        if (x < lines.front() || x > lines.back()) {
            continue;
        }
        if (!v[x].empty() && exists(v[x], y)) {
            ++ count;
            continue;
        }
        int left = 1, right = m, pos = m;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (lines[middle] >= x) {
                pos = middle;
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        -- pos;
        left = 0; right = place[pos].size() - 1; int last = 0;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (get_y(place[pos][middle], 1.0 * x) >= y) {
                last = middle;
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        if (last % 2 == 1 || (fabs(y - get_y(place[pos][last], 1.0 * x)) < 1.e-6)) {
            ++ count;
        }
    }
    fout << count << "\n";
    return 0;
}