#include using namespace std; #define x first #define y second #define pb push_back #define eb emplace_back #define rep(i,a,b) for(auto i = (a); i != (b); ++i) #define REP(i,n) rep(i,0,n) #define all(v) (v).begin(), (v).end() typedef long long ll; typedef long double ld; typedef pair ii; typedef vector vi; typedef vector vvi; typedef vector vii; const int maxn = 1e3 + 10; const int maxb = 2e3; const int maxCoord = 1e5; const ld EPS = 1e-7; int N, B; ii poly[2 * maxn]; int X[maxb], nballs[2 * maxn]; // x-position of balls vi E[2 * maxn]; bool will_keep[2 * maxn] = {}; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> B; rep(i, 1, N + 1) cin >> poly[i].x >> poly[i].y; rep(i, 1, N + 1) poly[N + i] = poly[i]; REP(i, B) cin >> X[i]; int minX = 1; rep(i, 1, N + 1) if (poly[i].x < poly[minX].x) minX = i; int maxX = minX; for (int i = minX; i < minX + N; i++) if (poly[i].x > poly[maxX].x) maxX = i; poly[minX - 1] = ii(-(maxCoord + 1), maxCoord + 1); poly[maxX + 1] = ii(+(maxCoord + 1), maxCoord + 1); /* cerr << "LOWER PART OF THE BOAT:" << endl; for (int i = minX; i <= maxX; i++) cerr << poly[i].x << ", " << poly[i].y << endl; */ vii order; for (int i = minX; i <= maxX; i++) order.eb(poly[i].x, i); sort(X, X + B); sort(all(order)); // i \in active <=> v[i] <-> v[i+1] active unordered_set active; active.insert(minX - 1); for (int i = minX; i < maxX; i++) { if (poly[i].y == poly[i + 1].y && poly[i].y <= 0) will_keep[i] = true; // horizontal stops stuff } for (int orderIt = 0, xIt = 0; xIt < B && orderIt < (int) order.size(); ) { // which one is first? if (X[xIt] < order[orderIt].x) { // find current lowest if (active.empty()) { xIt++; continue; } int lowest = -1; ld lowestY = maxCoord + 1; for (int i : active) { ld y = poly[i].y + (poly[i+1].y - poly[i].y) * (X[xIt] - poly[i].x) * ((ld) 1.0) / (poly[i+1].x - poly[i].x); if (y < lowestY) { lowest = i; lowestY = y; } } if (lowestY <= EPS) { // cerr << "Ball " << xIt << " at x=" << X[xIt] << " will hit " << lowest << endl; nballs[lowest]++; } xIt++; } else { assert(!active.empty()); int idx = order[orderIt++].y; int dy_l = poly[idx - 1].y - poly[idx].y; int dy_r = poly[idx + 1].y - poly[idx].y; int dx_l = poly[idx - 1].x - poly[idx].x; int dx_r = poly[idx + 1].x - poly[idx].x; // every x-position is unique: assert(dx_l != 0 && dx_r != 0); bool lleft = dx_l < 0, rleft = dx_r < 0; if (lleft != rleft) { // . // . // . if (dy_l < 0 && dy_r < 0) { // balls will stay in the middle. if (poly[idx].y <= 0) will_keep[idx - 1] = will_keep[idx] = true; } else if (dy_l < 0 && dy_r >= 0) { // balls from left flow upwards to right. E[idx].pb(idx - 1); } else if (dy_l >= 0 && dy_r < 0) { // balls from right flow upwards to left. E[idx - 1].pb(idx); } } else { // . // . // . // look up where the balls will end up. if (dy_l < 0 || dy_r < 0) { int lowest = -1; ld lowestY = maxCoord + 1; for (int i : active) { if (i == idx || i == idx - 1) continue; ld y = poly[i].y + (poly[i+1].y - poly[i].y) * (X[xIt] - poly[i].x) * ((ld) 1.0) / (poly[i+1].x - poly[i].x); if (poly[idx].y < y && y < lowestY) { lowest = i; lowestY = y; } } if (lowestY <= EPS) { if (dy_l < 0) E[lowest].pb(idx - 1); if (dy_r < 0) E[lowest].pb(idx); } } if (poly[idx].y <= 0 && dy_l < 0 && dy_r < 0) { if (lleft) will_keep[idx - 1] = true; else will_keep[idx] = true; } } if (lleft) active.erase(idx - 1); else active.insert(idx - 1); if (rleft) active.erase(idx); else active.insert(idx); } } queue q; for (int i = minX; i < maxX; i++) { if (will_keep[i]) { q.push(i); } } while (!q.empty()) { int cur = q.front(); q.pop(); for (int nxt : E[cur]) { if (will_keep[nxt]) continue; will_keep[nxt] = true; q.push(nxt); } } int ret = 0; for (int i = minX; i < maxX; i++) { if (will_keep[i]) { // cerr << "Edge " << i << " will stop it: " << nballs[i] << endl; ret += nballs[i]; } } cout << ret << endl; // cerr << ret << endl; return 0; }