Pagini recente » Cod sursa (job #3359227) | Cod sursa (job #3359211)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("poligon.in");
ofstream fout("poligon.out");
const int MAXC = 60000;
struct Point {
int x, y;
};
int n, m, ans;
vector<Point> p, q;
vector<int> query[MAXC + 5];
vector<int> ys;
bool used[MAXC + 5];
vector<int> sol;
int main() {
fin >> n >> m;
p.resize(n);
q.resize(m);
sol.resize(m);
for(int i = 0; i < n; i++) {
fin >> p[i].x >> p[i].y;
}
for(int i = 0; i < m; i++) {
fin >> q[i].x >> q[i].y;
query[q[i].y].push_back(i);
if(!used[q[i].y]) {
used[q[i].y] = 1;
ys.push_back(q[i].y);
}
}
for(int t = 0; t < (int)ys.size(); t++) {
int y = ys[t];
vector<int> ids = query[y];
vector<double> inter;
vector<pair<int, int> > oriz;
sort(ids.begin(), ids.end(), [&](int a, int b) {
return q[a].x < q[b].x;
});
for(int i = 0; i < n; i++) {
Point a = p[i];
Point b = p[(i + 1) % n];
if(a.y == b.y) {
if(a.y == y) {
oriz.push_back({min(a.x, b.x), max(a.x, b.x)});
}
continue;
}
Point jos = a;
Point sus = b;
if(jos.y > sus.y) {
swap(jos, sus);
}
if(jos.y <= y && y <= sus.y) {
long long den = sus.y - jos.y;
long long nr = 1LL * jos.x * den + 1LL * (y - jos.y) * (sus.x - jos.x);
if(nr % den == 0) {
int x = nr / den;
int poz = lower_bound(ids.begin(), ids.end(), x, [&](int id, int val) {
return q[id].x < val;
}) - ids.begin();
while(poz < (int)ids.size() && q[ids[poz]].x == x) {
sol[ids[poz]] = 1;
poz++;
}
}
}
if((a.y > y) != (b.y > y)) {
double x = a.x + 1.0 * (y - a.y) * (b.x - a.x) / (b.y - a.y);
inter.push_back(x);
}
}
sort(oriz.begin(), oriz.end());
for(int i = 0, j = 0; i < (int)oriz.size(); i++) {
while(j < (int)ids.size() && q[ids[j]].x < oriz[i].first) {
j++;
}
while(j < (int)ids.size() && q[ids[j]].x <= oriz[i].second) {
sol[ids[j]] = 1;
j++;
}
}
if((int)ids.size() <= 20) {
for(int i = 0; i < (int)ids.size(); i++) {
int id = ids[i];
if(sol[id]) continue;
int cnt = 0;
for(int j = 0; j < (int)inter.size(); j++) {
if(inter[j] > q[id].x) {
cnt++;
}
}
if(cnt % 2 == 1) {
sol[id] = 1;
}
}
} else {
sort(inter.begin(), inter.end());
for(int i = 0; i < (int)ids.size(); i++) {
int id = ids[i];
if(sol[id]) continue;
int poz = upper_bound(inter.begin(), inter.end(), q[id].x) - inter.begin();
int cnt = (int)inter.size() - poz;
if(cnt % 2 == 1) {
sol[id] = 1;
}
}
}
}
for(int i = 0; i < m; i++) {
ans += sol[i];
}
fout << ans << "\n";
return 0;
}