#include using namespace std; using vi = vector; using ll = long long; struct UnionFind { vi par, rank, size; int c; UnionFind(int n) : par(n), rank(n,0), size(n,1), c(n) { for (int i = 0; i < n; ++i) par[i] = i; } int find(int i) { return (par[i] == i ? i : (par[i] = find(par[i]))); } bool same(int i, int j) { return find(i) == find(j); } int get_size(int i) { return size[find(i)]; } int count() { return c; } void merge(int i, int j) { if ((i = find(i)) == (j = find(j))) return; c--; if (rank[i] > rank[j]) swap(i, j); par[i] = j; size[j] += size[i]; if (rank[i] == rank[j]) rank[j]++; } }; struct Line { ll x1, y1, x2, y2; }; ll gcd(ll a, ll b) { while (b) a %= b, swap(a, b); return a; } void normalize(ll &a, ll &b) { ll g = gcd(abs(a), abs(b)); a /= g, b /= g; if (b < 0) a *= -1, b *= -1; } pair probe_at(Line l, ll x) { ll n = l.y1 * (l.x2 - l.x1) + (l.y2 - l.y1) * (x - l.x1); ll d = l.x2 - l.x1; normalize(n, d); return {n, d}; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int B, N; cin >> N >> B; vector L; { int mi = 0; vi X(N), Y(N); for (int i = 0; i < N; ++i) { cin >> X[i] >> Y[i]; if (Y[i] > Y[mi]) mi = i; } std::rotate(X.begin(), X.begin()+mi, X.end()); std::rotate(Y.begin(), Y.begin()+mi, Y.end()); for (int i = 0; i < N; ++i) L.push_back(Line{X[i], Y[i], X[(i+1)%N], Y[(i+1)%N]}); } // Union segments that feed into each other. Dummy segment N represents // the surface at y>0. UnionFind uf(N+1); for (int i = 0; i < N; ++i) { if (L[i].y1 > 0 || L[i].y2 > 0) uf.merge(i, N); if (L[i].y1 == L[i].y2 || L[i].x1 >= L[i].x2) continue; ll x1 = (L[i].y1 > L[i].y2 ? L[i].x1 : L[i].x2); ll y1 = (L[i].y1 > L[i].y2 ? L[i].y1 : L[i].y2); int n = N; ll num = 1e6, den = 1LL; for (int j = 0; j < N; ++j) { if (j == i || x1 < L[j].x1 || L[j].x2 < x1) continue; if (L[j].x1 >= L[j].x2) continue; // Suppose a ball rises from x1, where will it hit // this segment? ll tnum, tden; tie(tnum, tden) = probe_at(L[j], x1); // First, if this is strictly less then y1, it's not interesting. // Normalization makes tden positive, so this should work: if (tnum < y1 * tden) continue; // Same for num/den, our current minimum. if (tnum * den > num * tden) continue; // Success. num = tnum, den = tden; n = j; } uf.merge(i, n); } // Find out the intervals that capture balls. map [x, y] to // capt[y] = x. Note: relies on integer coordinates. map capt; for (int i = 0; i < N; ++i) { if (uf.same(i, N)) continue; // cerr << "Capture at " << i // << " (" << L[i].x1 << ',' << L[i].y1 << "), " // << " (" << L[i].x2 << ',' << L[i].y2 << ")" << endl; ll x1 = L[i].x1, x2 = L[i].x2; for (int j = 0; j < N; ++j) { if (j == i || x2 < L[j].x1 || L[j].x2 < x1) continue; // These segments overlap. Test at an overlapping point to see // which is lower. ll xp = max(L[i].x1, L[j].x1); ll ni, di, nj, dj; tie(ni, di) = probe_at(L[i], xp); tie(nj, dj) = probe_at(L[j], xp); if (ni * dj <= nj * di) continue; // If j is lower we have to adjust [x1, x2]. if (j < i) x1 = max(x1, L[j].x2+1); if (j > i) x2 = min(x2, L[j].x1-1); } // cerr << "Final: " << x1 << " to " << x2 << endl; // Add to map. if (x1 > x2) continue; auto it = capt.find(x2); if (it == capt.end()) capt[x2] = x1; else it->second = min(it->second, x1); } int ans = B, x; while (B--) { cin >> x; auto it = capt.lower_bound(x); if (it == capt.end() || it->second > x) --ans; } cout << ans << endl; return 0; }