/* Solution to Floats. * * Floats up per ball, which is too slow. * * Expected answer: TLE. * */ #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 balls(B); for(int i = 0; i < N; i++) { cin >> iceberg[i].x >> iceberg[i].y; } 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); vector> float_from(N); for(int i = 0; i < N; i++) { // We can skip "top edges". if(ib(i).x > ib(i+1).x) continue; // If the edge is flat, we're done. if(ib(i).y == ib(i+1).y) { surface[i] = ib(i).y > 0; continue; } // The case where the ball floats left: 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) // It goes left-down, we get stuck. surface[i] = ib(i).y > 0; else // It goes left up, so we float there. float_from[(i-1 + N)%N].push_back(i); } // 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. surface[i] = ib(i).y > 0; } else { // The case where the ball actually floats up. int int_idx = float_to(ib(i)); if(int_idx == -1) surface[i] = true; else float_from[int_idx].push_back(i); } } // If we aren't floating left, we're floating right. // So ib(i).y < ib(i+1).y. else { // Same cases as above: if the next line goes further right we get // stuck or float to that edge. if(ib(i+1).x < ib(i+2).x) { if(ib(i+1).y > ib(i+2).y) surface[i] = ib(i+1).y > 0; else float_from[(i+1)%N].push_back((i)%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))) { surface[i] = ib(i + 1).y > 0; } // The ball actually floats up on the right: else { int int_idx = float_to(ib(i+1)); if(int_idx == -1) surface[i] = true; else float_from[int_idx].push_back(i); } } } // From the edges from which we know balls surface, let's propagate that // fact down the iceberg. queue q; for(int i = 0; i < N; i++) if(surface[i]) q.push(i); while(!q.empty()) { int cur = q.front(); q.pop(); for(int nb : float_from[cur]) { surface[nb] = true; q.push(nb); } } int surface_count = 0; for(int i = 0; i < B; i++) { pt ball; ball.x = balls[i]; ball.y = -1000000; int int_idx = float_to(ball); if(int_idx == -1 || surface[int_idx]) surface_count ++; } cout << B- surface_count << endl; return 0; }