// Ported from Timon! Since that was a very fast solution // But somewhere I made a mistake, so it is WA :(... ??? import java.util.*; public class JoshuaFloats { Scanner s = new Scanner(System.in); public static void main(String[] args) { (new JoshuaFloats()).solve(); } void solve() { int N = s.nextInt(); int B = s.nextInt(); List L = new ArrayList<>(); { long[] X = new long[N]; long[] Y = new long[N]; int maxi = 0; for(int i = 0; i < N; i++) { X[i] = s.nextInt(); Y[i] = s.nextInt(); if(Y[i] > Y[maxi]) maxi = i; } for(int i = maxi; i < N; i++) { L.add(new long[] {X[i], Y[i], X[(i + 1) % N], Y[(i + 1) % N]}); } for(int i = 0; i < maxi; i++) { L.add(new long[] {X[i], Y[i], X[(i + 1) % N], Y[(i + 1) % N]}); } } UnionFind uf = new UnionFind(N + 1); for(int i = 0; i < N; i++) { if(L.get(i)[1] > 0 || L.get(i)[3] > 0) uf.merge(i, N); if(L.get(i)[1] == L.get(i)[3] || L.get(i)[0] >= L.get(i)[2]) continue; long x1 = (L.get(i)[1] > L.get(i)[3] ? L.get(i)[0] : L.get(i)[2]); long y1 = (L.get(i)[1] > L.get(i)[3] ? L.get(i)[1] : L.get(i)[3]); int n = N; long num = 1000000, den = 1; for(int j = 0; j < N; j++) { if(j == i || x1 < L.get(j)[0] || L.get(j)[2] < x1) continue; if(L.get(j)[0] >= L.get(j)[2]) continue; // Suppose a ball rises from x1, where will it hit // this segment? long[] bla = probe_at(L.get(j), x1); long tnum = bla[0], tden = bla[1]; // 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; } // Verify that we don't get stuck in a crevice. if(isCrevice(L.get((i + N - 1) % N), L.get(i)) || isCrevice(L.get(i), L.get((i + 1) % N))) continue; uf.merge(i, n); } // Find out the intervals that capture balls. map [x, y] to // capt[y] = x. Note: relies on integer coordinates. TreeMap capt = new TreeMap<>(); for(int i = 0; i < N; i++) { if(uf.same(i, N)) continue; long x1 = L.get(i)[0], x2 = L.get(i)[2]; for(int j = 0; j < N; j++) { if(j == i || x2 < L.get(j)[0] || L.get(j)[2] < x1) continue; // These segments overlap. Test at an overlapping point to see // which is lower. long xp = Math.max(L.get(i)[0], L.get(j)[0]); long[] bar = probe_at(L.get(i), xp); long[] foo = probe_at(L.get(j), xp); long ni = bar[0], di = bar[1], nj = foo[0], dj = foo[1]; if(ni * dj <= nj * di) continue; // If j is lower we have to adjust [x1, x2]. if(j < i) x1 = Math.max(x1, L.get(j)[2] + 1); if(j > i) x2 = Math.min(x2, L.get(j)[0] - 1); } // Add to map. if(x1 > x2) continue; Long bla = capt.get(x2); if(bla == null) { capt.put(x2, x1); } else { capt.put(x2, Math.min(bla, x1)); } } int ans = 0; for(int i = 0; i < B; i++) { long x = s.nextLong(); Map.Entry it = capt.ceilingEntry(x); // System.err.println(x); // System.err.println(it == null ? -1 : it.getKey()); if(it == null || it.getValue() > x) { ++ans; } } System.out.println(B - ans); } static class UnionFind { int[] par; int[] rank; int[] size; int c; UnionFind(int n) { par = new int[n]; rank = new int[n]; size = new int[n]; for(int i = 0; i < n; i++) { par[i] = i; rank[i] = 0; size[i] = 1; } c = n; } int find(int i) { return (par[i] == i ? i : (par[i] = find(par[i]))); } boolean 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]) { int t = i; i = j; j = t; } par[i] = j; size[j] += size[i]; if(rank[i] == rank[j]) rank[j]++; } } long gcd(long a, long b) { while(b != 0) { a %= b; long t = a; a = b; b = t; } return a; } void normalise(long[] r) { long g = gcd(Math.abs(r[0]), Math.abs(r[1])); r[0] /= g; r[1] /= g; if(r[1] < 0) { r[0] *= -1; r[1] *= -1; } } long[] probe_at(long[] l, long x) { long n = l[1] * (l[2] - l[0]) + (l[3] - l[1]) * (x - l[0]); long d = l[2] - l[0]; long[] ret = new long[] {n, d}; normalise(ret); return ret; } boolean isCrevice(long[] l1, long[] l2) { long d = (l1[0] - l1[2]) * (l2[3] - l2[1]) - (l2[2] - l2[0]) * (l1[1] - l1[3]); return l1[1] <= l1[3] && l2[1] >= l2[3] && d >= 0; } }