#include #include #include using namespace std; struct pt { int x; int y; }; // Returns the slope of the line to through points with different // x coordinates. double slope(pt a, pt b) { return (1.0 * b.y - a.y) / (b.x - a.x); } int N, B; vector iceberg; pt ib(int i) { i %= N; if(i < 0) i += N; return iceberg[i]; } // If you float up from cur, which edge in the iceberg do you hit? // Returns -1 if the ball floats off. int float_to(pt cur) { double best_y = 100000000; int best_idx = -1; for(int j = 0; j < N; j++) { // Only use edges that share an x coordinate with our // floating-off point. if(!(ib(j).x < cur.x && ib(j + 1).x > cur.x)) continue; // The y-value at our floating off x-coord: double y_int = slope(ib(j), ib(j + 1)) * (cur.x - ib(j).x) + ib(j).y; if(y_int > cur.y && y_int < best_y) { best_y = y_int; best_idx = j; } } return best_idx; } int main() { // Read all the input. cin >> N >> B; iceberg = vector(N); vector bounds(N + 1); vector balls(B); bounds[N] = 1000000; for(int i = 0; i < N; i++) { cin >> iceberg[i].x >> iceberg[i].y; bounds[i] = iceberg[i].x; } // Bounds contain the right bounds of "bins" for the balls. sort(bounds.begin(), bounds.end()); for(int i = 0; i < B; i++) { cin >> balls[i]; } sort(balls.begin(), balls.end()); // For edges, we use index i for the edge from ib(i) to ib(i+1). vector surface(N, false); int local_ct = 0; int ball_idx = 0; for(int bound_idx = 0; bound_idx <= N; bound_idx++) { int localer_ct = 0; int bound = bounds[bound_idx]; while(ball_idx < B && balls[ball_idx] < bound) { localer_ct++; ball_idx++; } pt ball_pt; ball_pt.x = bound - 1; ball_pt.y = -10000000; int edge = float_to(ball_pt); if(edge == -1) { local_ct += localer_ct; continue; } int i = edge; while(true) { // cerr << "At edge " << i << endl; if(ib(i).y == ib(i + 1).y) { if((ib(i).y > 0)) local_ct += localer_ct; break; } if(ib(i).y > ib(i + 1).y) { if(ib(i - 1).x < ib(i).x) { // The next line also goes left. if(ib(i - 1).y < ib(i).y) { if((ib(i).y > 0)) local_ct += localer_ct; break; } else // It goes left up, so we float there. i = (i - 1 + N) % N; } // So the next line goes right... else if(slope(ib(i), ib(i + 1)) > slope(ib(i), ib(i - 1))) { // Stuck in a corner again. if((ib(i).y > 0)) local_ct += localer_ct; break; } else { // The case where the ball actually floats up. int int_idx = float_to(ib(i)); if(int_idx == -1) { local_ct += localer_ct; break; } else { i = int_idx; } } } else { if(ib(i + 1).x < ib(i + 2).x) { if(ib(i + 1).y > ib(i + 2).y) { if(ib(i + 1).y > 0) { local_ct += localer_ct; } break; } else { i = (i + 1) % N; } } // If the line goes back left we can still get stuck in a corner. else if(slope(ib(i), ib(i + 1)) < slope(ib(i + 2), ib(i + 1))) { if(ib(i + 1).y > 0) { local_ct += localer_ct; } break; } else { int int_idx = float_to(ib(i + 1)); if(int_idx == -1) { local_ct += localer_ct; break; } else { i = int_idx; } } } } } cout << B - local_ct << endl; return 0; }