Pagini recente » Cod sursa (job #263352) | Cod sursa (job #2058678)
#include <bits/stdc++.h>
using namespace std;
struct Point {
int x, y;
complex<int> toc() { return complex<int>(x, y); }
};
int main() {
ifstream cin("poligon.in");
ofstream cout("poligon.out");
int n, m; cin >> n >> m;
vector<Point> poly(n);
vector<int> xs;
for (int i = 0; i < n; ++i) {
cin >> poly[i].x >> poly[i].y;
xs.push_back(poly[i].x);
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
vector<vector<pair<Point, Point>>> lines(xs.size());
vector<map<int, int>> verts(xs.size());
auto ins_segm = [&](Point a, Point b) {
if (a.x > b.x) swap(a, b);
if (a.x == b.x) {
int idx = lower_bound(xs.begin(), xs.end(), a.x) - xs.begin();
verts[idx][min(a.y, b.y)] = max(a.y, b.y);
}
for (int i = 0; i < (int)xs.size(); ++i) {
if (xs[i] >= a.x && xs[i] < b.x)
lines[i].emplace_back(a, b);
}
};
for (int i = 0, j = n - 1; i < n; j = i++)
ins_segm(poly[j], poly[i]);
auto eval = [](Point a, Point b, int x) {
// (x - a.x) / (b.x - a.x) = (y - a.y) / (b.y - a.y)
long long up = 1LL * a.y * (b.x - a.x)
+ 1LL * (x - a.x) * (b.y - a.y);
long long dw = b.x - a.x;
return make_pair(up, dw);
};
int cmp_x;
auto cmp = [&](pair<Point, Point> a, pair<Point, Point> b) {
auto r1 = eval(a.first, a.second, cmp_x),
r2 = eval(b.first, b.second, cmp_x);
return r1.first * r2.second > r1.second * r2.first;
};
for (int i = 0; i < (int)lines.size(); ++i) {
cmp_x = xs[i];
sort(lines[i].begin(), lines[i].end(), cmp);
}
int tot = 0;
for (int i = 0; i < m; ++i) {
Point p; cin >> p.x >> p.y;
int idx = upper_bound(xs.begin(), xs.end(), p.x)
- xs.begin() - 1;
// Check against verts
if (xs[idx] == p.x) {
auto it = verts[idx].upper_bound(p.y);
if (it != verts[idx].begin() && prev(it)->second >= p.y) {
// On polygon
tot += 1;
continue;
}
}
cmp_x = p.x;
auto it = lower_bound(lines[idx].begin(), lines[idx].end(),
make_pair(Point{p.x, p.y}, Point{p.x + 1, p.y}), cmp);
if (it != lines[idx].end()) {
auto yn = eval(it->first, it->second, p.x);
if (yn.first == yn.second * p.y) {
// On polygon
tot += 1;
continue;
}
}
tot += distance(it, lines[idx].end()) % 2;
}
cout << tot << endl;
return 0;
}