Cod sursa(job #1718143)

Utilizator veleanduAlex Velea veleandu Data 16 iunie 2016 19:37:00
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.52 kb
#include <cassert>
#include <cmath>

#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 10005;
const int MAX_COORD = 3000002;
const double EPSILON = 1.e-7;
struct Point {
    int x, y;
} points[MAX_N];
vector<int> slacksX;
vector<int> slacks[MAX_N];
vector<int> pointSlacks[MAX_COORD];
vector< pair<int, int> > lines[MAX_COORD];
int countSlacks;
double referenceX;

double getY(int index, double x) {
    double x1 = points[index - 1].x, y1 = points[index - 1].y;
    double x2 = points[index].x, y2 = points[index].y;
    return y1 + (x - x1) / (x2 - x1) * (y2 - y1);
}

void computeSlack(int index, int n) {
    int xLeft = slacksX[index - 1];
    int xRight = slacksX[index];
    for (int i = 1; i <= n; ++ i) {
        if ((points[i - 1].x <= xLeft && xRight <= points[i].x) ||
                (points[i].x <= xLeft && xRight <= points[i - 1].x)) {
            slacks[index].push_back(i);
        }
    }
    referenceX = (xLeft + xRight) * 0.5;
    sort(slacks[index].begin(), slacks[index].end(), [](const int &i, const int &j) {
        return getY(i, referenceX) < getY(j, referenceX);
    });
}

void computePointSlack(int x, int n) {
    for (int i = 1; i <= n; ++ i) {
        if ((points[i - 1].x <= x && x < points[i].x) || (points[i - 1].x > x && x >= points[i].x)
            ) {
            pointSlacks[x].push_back(i);
        }
    }
    referenceX = x;
    sort(pointSlacks[x].begin(), pointSlacks[x].end(), [](const int &i, const int &j) {
        return getY(i, referenceX) < getY(j, referenceX);
    });
}

void computeSlacks(int n) {
    points[0] = points[n];
    points[n + 1] = points[1];
    for (int i = 1; i <= n; i += 1) {
        if (points[i].x == points[i - 1].x) {
            lines[points[i].x].push_back(make_pair(min(points[i].y, points[i - 1].y),
                                                    max(points[i].y, points[i - 1].y)));
        }
    }
    for (int i = 1; i <= n; i += 1) {
        if (points[i].x != points[i - 1].x && points[i].x != points[i + 1].x) {
            lines[points[i].x].push_back(make_pair(points[i].y, points[i].y));
        }
    }
    for (int i = 0; i < MAX_COORD; i += 1) {
        sort(lines[i].begin(), lines[i].end());
    }
    for (int i = 1; i <= n; i += 1) {
        slacksX.push_back(points[i].x);
    }
    sort(slacksX.begin(), slacksX.end());
    slacksX.erase(unique(slacksX.begin(), slacksX.end()), slacksX.end());
    countSlacks = slacksX.size() - 1;
    for (int i = 1; i <= countSlacks; i += 1) {
        computeSlack(i, n);
    }
    for (int i = 0; i <= countSlacks; i += 1) {
        computePointSlack(slacksX[i], n);
    }
}

int searchInLine(int x, int y) {
    if (lines[x].empty() || lines[x].back().second < y) {
        return 0;
    }
    int left = 0, right = lines[x].size() - 1, last = lines[x].size() - 1;
    while (left <= right) {
        int middle = (left + right) / 2;
        if (lines[x][middle].second >= y) {
            last = middle;
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
    return lines[x][last].first <= y;
}

int searchInSlack(int index, int x, int y) {
    if (getY(slacks[index][0], x) - y >= EPSILON || getY(slacks[index].back(), x) - y <= -EPSILON) {
        return 0;
    }
    int left = 0, right = slacks[index].size() - 1, last = 0;
    while (left <= right) {
        int middle = (left + right) / 2;
        if (fabs(getY(slacks[index][middle], x) - y) < EPSILON) {
            return 1;
        }
        if (getY(slacks[index][middle], x) - y <= -EPSILON) {
            last = middle;
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    if (fabs(getY(slacks[index][last], x) - y) < EPSILON) {
        return 1;
    }
    return last % 2 == 0;
}

int searchInPointSlack(int x, int y) {
    
    if (pointSlacks[x].empty()) {
        return 0;
    }
    int left = 0, right = pointSlacks[x].size() - 1, last = -1;
    while (left <= right) {
        int middle = (left + right) / 2;
        if (fabs(getY(pointSlacks[x][middle], x) - y) < EPSILON) {
            return 1;
        }
        if (getY(pointSlacks[x][middle], x) - y <= -EPSILON) {
            last = middle;
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    if (last != -1 && fabs(getY(pointSlacks[x][last], x) - y) < EPSILON) {
        return 1;
    }
    return last % 2 == 0;
}

int main() {
    //ifstream cin("f.in");
    ifstream cin("poligon.in");
    ofstream cout("poligon.out");
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i += 1) {
        cin >> points[i].x >> points[i].y;
    }
    computeSlacks(n);
    int answer = 0;
    for (int i = 1; i <= m; i += 1) {
        Point p;
        cin >> p.x >> p.y;
        int left = 0, right = slacksX.size(), last = -1;
        if (p.x < slacksX[0] || p.x > slacksX.back()) {
            continue;
        }
        while (left <= right) {
            int middle = (left + right) / 2;
            if (slacksX[middle] >= p.x) {
                last = middle;
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        if (slacksX[last] == p.x) {
            answer += (searchInLine(p.x, p.y) || searchInPointSlack(p.x, p.y));
            //cout << (searchInLine(p.x, p.y) || searchInPointSlack(p.x, p.y)) << "\n";
        } else {
            answer += searchInSlack(last, p.x, p.y);
            //cout << searchInSlack(last, p.x, p.y) << "\n";
        }
    }
    cout << answer << "\n";
    return 0;
}