#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; for(int ball = 0; ball < B; ball++) { // cerr << "Doing ball " << ball << endl; // cerr << "The one at " << balls[ball] << endl; // cerr << "Before, local_ct = " << local_ct << endl; pt ball_pt; ball_pt.x = balls[ball]; ball_pt.y = -10000000; int edge = float_to(ball_pt); if(edge == -1) { local_ct++; continue; } int prev_edge = -1; int i = edge; while(true) { // cerr << "At edge " << i << endl; // cerr << "The one that goes from " << ib(i).x << " " << ib(i).y; // cerr << " to " << ib(i+1).x << " " << ib(i+1).y << endl; if(i == prev_edge) break; prev_edge = i; if(ib(i).y == ib(i + 1).y) { local_ct += (ib(i).y > 0); 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) { local_ct += (ib(i).y > 0); 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. local_ct += (ib(i).y > 0); break; } else { // The case where the ball actually floats up. int int_idx = float_to(ib(i)); if(int_idx == -1) { local_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) { local_ct += (ib(i + 1).y > 0); 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))) { local_ct += (ib(i + 1).y > 0); } else { int int_idx = float_to(ib(i + 1)); if(int_idx == -1) { local_ct++; break; } else { i = int_idx; } } } } } cout << B - local_ct << endl; return 0; }