Pagini recente » Cod sursa (job #2690687) | Cod sursa (job #1309304) | Cod sursa (job #327385) | Cod sursa (job #2104523) | Cod sursa (job #2514094)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define dbg(x) cerr << #x << " " << x << "\n"
#define pb push_back
const int N = 800;
struct Point {
int x;
int y;
};
Point a[1 + N + 1];
int oriz[1 + N + 1];
vector <int> v[1 + N];
double med;
bool inside (int x1, int x2, int y1, int y2) {
if (x2 <= x1 && y1 <= y2)
return true;
if (y2 <= x1 && y1 <= x2)
return true;
return false;
}
double calc (Point a, Point b, double med) {
return a.y + 1.0 * (b.y - a.y) * (med - a.x) / (b.x - a.x);
}
bool cmp (int x, int y) {
return calc (a[x], a[x + 1], med) < calc (a[y], a[y + 1], med);
}
ll area (Point a, Point b, Point c) {
return 1ll * a.x * b.y + 1ll * b.x * c.y + 1ll * c.x * a.y - 1ll * a.y * b.x - 1ll * b.y * c.x - 1ll * c.y * a.x;
}
bool ok;
bool check (int x, Point p) {
ll det;
if (a[x].x < a[x + 1].x || (a[x].x == a[x + 1].x && a[x].y < a[x + 1].y))
det = area (a[x], a[x + 1], p);
else
det = area (a[x + 1], a[x], p);
if (det == 0)
ok = true;
return det >= 0;
}
int main () {
freopen ("poligon.in", "r", stdin);
freopen ("poligon.out", "w", stdout);
ios::sync_with_stdio (false);
cin.tie (0); cout.tie (0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].y;
oriz[i] = a[i].x;
}
a[n + 1] = a[1];
sort (oriz + 1, oriz + n + 1);
int nx = 0;
oriz[0] = -1;
for (int i = 1; i <= n; i++)
if (oriz[nx] != oriz[i])
oriz[++nx] = oriz[i];
oriz[nx + 1] = oriz[nx] + 100000;
for (int i = 1; i <= nx; i++) {
for (int j = 1; j <= n; j++)
if (inside (oriz[i], a[j].x, oriz[i + 1], a[j + 1].x))
v[i].pb (j);
med = (oriz[i] + oriz[i + 1]) / 2.0;
sort (v[i].begin (), v[i].end (), cmp);
}
int ans = 0;
for (int i = 1; i <= m; i++) {
Point p;
cin >> p.x >> p.y;
int l = 1, r = nx;
int best = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (oriz[mid] < p.x)
best = mid, l = mid + 1;
else
r = mid - 1;
}
int nr = -1;
l = 0, r = v[best].size () - 1;
ok = false;
while (l <= r) {
int mid = (l + r) / 2;
if (check (v[best][mid], p))
nr = mid, l = mid + 1;
else
r = mid - 1;
}
if (nr % 2 == 0 || ok)
ans++;
}
cout << ans << "\n";
return 0;
}