import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Scanner; import java.util.TreeSet; import java.util.Set; class Edge { int lx, ly, ux, uy; double slope; public Edge(int x1, int y1, int x2, int y2) { if(y1 <= y2) { lx = x1; ly = y1; ux = x2; uy = y2; } else { lx = x2; ly = y2; ux = x1; uy = y1; } slope = (y1 - y2 + 0.0d)/(x1 - x2 + 0.0d); } } public class HarryPreprocessingNoBinning { static int N, B; static Edge[] edges; static int[] next; static int Intersect(int xpos, int ypos) // What is the next edge the ball hits when it starts here? { double yintersect = 100000; int index = -1; for(int i = 0; i < N; i++) { Edge cur = edges[i]; int minx = Math.min(cur.lx, cur.ux); int maxx = Math.max(cur.lx, cur.ux); if(minx < xpos && maxx > xpos) { double y = (xpos - minx) * cur.slope + ((minx == cur.lx) ? cur.ly : cur.uy); if((y < yintersect) && y > ypos) { yintersect = y; index = i; } } } //if(yintersect > 0) return -1; return index; } static void FindNext(int i) // -1 means free, -2 means stuck. { if(edges[i].uy > 0) { next[i] = -1; return; } // The ball ends above water. if(edges[i].uy == edges[i].ly) { next[i] = -2; return; } // The surface is flat; the ball gets stuck. // Case: increasing -> search in positive x-direction. if(edges[i].lx < edges[i].ux) { // Next edge goes forward, edge is decreasing -> ball gets stuck. /\ if(edges[(i+1)%N].lx > edges[i].ux) { next[i] = -2; return; } // Next edge goes forward, edge is increasing -> ball continues. // if(edges[(i+1)%N].ux > edges[i].ux) { next[i] = ((i+1)%N); return; } // Next edge goes backward. Again, we have two cases, depending on the slopes: if(edges[(i+1)%N].slope < edges[i].slope) // If the new slope is smaller than the current slope, the ball is (temporarily) free from the iceberg. We find a new intersection point. { next[i] = Intersect(edges[i].ux, edges[i].uy); return; } if(edges[(i+1)%N].slope > edges[i].slope) // If the new slope is greater than the current slope, the ball is trapped. { next[i] = -2; return; } return; } // Case: decreasing -> search in negative x-direction. if(edges[i].lx > edges[i].ux) { int j = (i - 1 + N) % N; // Next edge goes in the same direction, edge is decreasing as well -> ball continues \\ if(edges[j].ux < edges[i].ux) { next[i] = j; return; } //Next edge goes forward, edge is increasing -> ball gets stuck. /\ if(edges[j].lx < edges[i].ux) { next[i] = -2; return; } // Edge goes backward. Two cases: if(edges[j].slope > edges[i].slope) // If the new slope is greater, the ball temporarily breaks free from the iceberg. { next[i] = Intersect(edges[i].ux, edges[i].uy); return; } if(edges[j].slope < edges[i].slope) // If the new slope is smaller, then the ball is trapped. { next[i] = -2; return; } } return; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); B = sc.nextInt(); edges = new Edge[N]; next = new int[N]; int[] balls = new int[B]; int x,y; int prevx = 0, prevy = 0; int firstx = 0, firsty = 0; for(int i = 0; i < N; i++) { x = sc.nextInt(); y = sc.nextInt(); if(i == 0) { firstx = x; firsty = y; } if(i != 0) { edges[i - 1] = new Edge(x, y, prevx, prevy); } prevx = x; prevy = y; } edges[N - 1] = new Edge(prevx, prevy, firstx, firsty); for(int b = 0; b < B; b++) balls[b] = sc.nextInt(); for(int i = 0; i < N; i++) FindNext(i); for(int a = 0; a < N; a++) for(int i = 0; i < N; i++) if(next[i] != -1 && next[i] != -2) next[i] = next[next[i]]; int total = 0; for(int b = 0; b < B; b++) { int start = balls[b]; int edge = Intersect(start, -100000000); if(edge == -1) // The ball never touches the iceberg. total++; else if(next[edge] == -1) // The ball touches the iceberg, but it manages to escape. total++; } System.out.println(B - total); return; } }