Pagini recente » Cod sursa (job #653058) | Cod sursa (job #856624) | Cod sursa (job #1545389) | Cod sursa (job #3238184) | Cod sursa (job #597325)
Cod sursa(job #597325)
#include <stdio.h>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_N 810
#define MAX_C 60010
#define mp make_pair
int n, m, T, nrV, nrE, sol;
int P[MAX_N], stop[MAX_N];
int sector[MAX_C];
vector <int> E[MAX_N];
set <pair <int, int> > V[MAX_C];
struct punct {
int x, y;
} A[MAX_N], Q;
double midX;
inline int next(int x) {
if (x < n)
return x + 1;
return 1;
}
inline double coordY(int i) {
double m = 1.0 * (A[i].y - A[next(i)].y) / (A[i].x - A[next(i)].x);
double n = A[i].y - m * A[i].x;
return m * midX + n;
}
inline int cmp(int p, int q) {
return coordY(p) < coordY(q);
}
void solve() {
sort(P + 1, P + n + 1);
int m = unique(P + 1, P + n + 1) - P - 1;
for (int i = 1; i <= n; i++) {
if (A[i].x != A[next(i)].x) {
for (int j = 1; j < m; j++)
if (min(A[i].x, A[next(i)].x) <= P[j] && P[j + 1] <= max(A[i].x, A[next(i)].x))
E[j].push_back(i);
}
else
V[A[i].x].insert(mp(min(A[i].y, A[next(i)].y), max(A[i].y, A[next(i)].y)));
V[A[i].x].insert(mp(A[i].y, A[i].y));
}
for (int i = 1; i < m; i++) {
sector[P[i]] = i;
midX = (P[i] + P[i + 1]) / 2.0;
sort(E[i].begin(), E[i].end(), cmp);
}
for (int i = 0; i < P[m]; i++)
if (i > 0 && sector[i] == 0)
sector[i] = sector[i - 1];
}
inline int sgn(punct A, punct B, punct C) {
if (A.x > B.x)
swap(A, B);
int ans = A.x * B.y + B.x * C.y + C.x * A.y - A.x * C.y - B.x * A.y - C.x * B.y;
if (ans < 0)
return -1;
if (ans > 0)
return 1;
return 0;
}
int ans() {
if (V[Q.x].size()) {
set <pair <int, int> >::iterator it = V[Q.x].upper_bound(mp(Q.y, Q.y));
if (it != V[Q.x].begin()) {
--it;
if (it->first <= Q.y && Q.y <= it->second)
return 1;
}
}
int ind = sector[Q.x];
if (ind && E[ind].size()) {
int L = E[ind].size() - 1, pos = -1;
for (int i = 9; i >= 0; i--) {
pos += 1 << i;
if (pos <= L && sgn(A[E[ind][pos]], A[next(E[ind][pos])], Q) >= 0)
pos += 1 << i;
pos -= 1 << i;
}
if (pos >= 0 && ((L - pos) % 2 == 1 || sgn(A[E[ind][pos]], A[next(E[ind][pos])], Q) == 0))
return 1;
}
return 0;
}
int main() {
freopen("poligon.in", "r", stdin);
freopen("poligon.out", "w", stdout);
scanf("%d %d", &n, &T);
for (int i = 1; i <= n; i++) {
scanf("%d %d", &A[i].x, &A[i].y);
P[i] = A[i].x;
}
solve();
int sol = 0;
for (int i = 1; i <= T; i++) {
scanf("%d %d", &Q.x, &Q.y);
sol += ans();
}
printf("%d\n", sol);
return 0;
}