Pagini recente » Cod sursa (job #348286) | Cod sursa (job #2717955) | Cod sursa (job #1529690) | Cod sursa (job #2897120) | Cod sursa (job #3300277)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("poligon.in");
ofstream fout("poligon.out");
typedef long long ll;
const int N = 805;
struct Edge {
int x1, y1, x2, y2;
} v[N];
pair<int, int> f[N];
int n, m, x, y, rasp;
bool valid(int x, int y) {
bool onBoundary = false;
int nr = 0;
for (int i = 1; i <= n; i++) {
int x1 = v[i].x1, y1 = v[i].y1;
int x2 = v[i].x2, y2 = v[i].y2;
ll cross = (ll)(x - x1) * (ll)(y2 - y1) - (ll)(y - y1) * (ll)(x2 - x1);
if (cross == 0) {
if (x >= min(x1, x2) && x <= max(x1, x2) && y >= min(y1, y2) && y <= max(y1, y2)) {
onBoundary = true;
break;
}
}
if (y1 == y2)
continue;
bool above1 = (y1 > y);
bool above2 = (y2 > y);
if (above1 == above2)
continue;
ll A = (ll)x1 * y2 - (ll)x2 * y1 + (ll)y * (x2 - x1);
ll denom = y2 - y1;
if (denom > 0) {
if (A <= (ll)x * denom)
nr++;
} else {
if (A >= (ll)x * denom)
nr++;
}
}
if (onBoundary)
return false;
return (nr % 2 == 1);
}
int main() {
fin >> n >> m;
for (int i = 1; i <= n; i++)
fin >> f[i].first >> f[i].second;
for (int i = 1; i <= n-1; i++) {
v[i] = { f[i].first, f[i].second, f[i+1].first, f[i+1].second };
}
v[n] = { f[n].first, f[n].second, f[1].first, f[1].second };
rasp = 0;
while (m--) {
fin >> x >> y;
if (valid(x, y))
rasp++;
}
fout << rasp << '\n';
fin.close();
fout.close();
return 0;
}