Pagini recente » Cod sursa (job #1478261) | Cod sursa (job #1229091) | Cod sursa (job #770728) | Cod sursa (job #1832990) | Cod sursa (job #2407448)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 810;
int x[MAXN];
int y[MAXN];
/// y1 + dx / dy * (x-x1) > y2 + dx / dy *(x-x1)
long double eval(int i, long double xx) {
if(x[i] == x[i+1]) return min(y[i], y[i+1]);
if(y[i] == y[i+1]) return y[i];
return 1.0*y[i] + ((1.0*x[i+1]-1.0*x[i])/(1.0*y[i+1]-1.0*y[i]))*(1.0*xx-1.0*x[i]);
}
bool intre(int a, int b, int c) {
if(a > b) swap(a, b);
return c >= a && c <= b;
}
bool collinear(int i, int xx, int yy) {
return (1.0*(1.0*yy-1.0*y[i])*1.0*(1.0*x[i+1]-1.0*x[i]) == 1.0*(1.0*y[i+1]-1.0*y[i])*1.0*(1.0*xx-1.0*x[i])) && intre(x[i], x[i+1], xx) && intre(y[i], y[i+1], yy);
}
int main() {
#ifdef BLAT
freopen("input", "r", stdin);
#else
freopen("poligon.in", "r", stdin);
freopen("poligon.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
srand(time(nullptr));
int n, m;
cin >> n >> m;
vector< int > startFasii;
startFasii.emplace_back(1e9);
for(int i = 0; i < n; ++i) {
cin >> x[i] >> y[i];
startFasii.emplace_back(x[i]);
}
x[n] = x[0];
y[n] = y[0];
sort(startFasii.begin(), startFasii.end());
startFasii.erase(unique(startFasii.begin(), startFasii.end()), startFasii.end());
vector< vector< int> > interest(startFasii.size() + 1);
for(int i = 0; i < startFasii.size() - 1; ++i) {
for(int j = 0; j < n; ++j) {
int x1 = x[j], x2 = x[j+1];
if(x2 < x1) swap(x1, x2);
if(x1 <= startFasii[i] && x2 >= startFasii[i]) {
interest[i].emplace_back(j);
if(x1 == x2) interest[i].emplace_back(j);
}
}
}
for(int i = 0; i < startFasii.size(); ++i) {
sort(interest[i].begin(), interest[i].end(), [&](int a, int b) -> bool {
return eval(a, startFasii[i] + 0.5) < eval(b, startFasii[i] + 0.5);
});
}
int ans = 0;
// for(int i = 0; i < startFasii.size(); ++i) {
// cout << i << ' ' << startFasii[i] << ' ';
// for(auto &x : interest[i]) cout << x << ' ';
// cout << '\n';
// }
const long double eps = 1e-8;
for(int i = 0; i < m; ++i) {
int xx, yy;
cin >> xx >> yy;
int fasie = 0;
for(int step = 20; step >= 0; --step) {
if(fasie + (1<<step) < startFasii.size() && startFasii[fasie+(1<<step)] <= xx) {
fasie += (1<<step);
}
}
if(xx < startFasii[0]) continue;
// cout << xx << ' ' << yy << " e pe fasia " << fasie << '\n';
int where = -1;
bool ok = false;
for(int step = 20; step >= 0; --step) {
if(where + (1<<step) < interest[fasie].size()) {
if(collinear(interest[fasie][where+(1<<step)], xx, yy)) {
ok = true;
}
if(eval(interest[fasie][where+(1<<step)], xx) < 1.0*yy + eps) {
where += (1<<step);
}
}
}
// cout << i << ' ' << where << '\n';
if(ok || (where%2==0)) {
// cout << i << '\n';
ans ++;
}
}
cout << ans << '\n';
return 0;
}