Floating Points

Your ship has sunk. You want it back.

The best way1 to salvage a shipwreck is to release a whole bunch of ping pong balls beneath it. The ping pong balls float up towards the surface, and their buoyancy takes the sunken ship up towards the surface with them. At least, they do that as long as the ping pong balls actually push the ship up: if they slide off the shipwreck, or float past it entirely, or even surface in an inside air bubble of the ship, they of course do not contribute to pushing the ship out of the water.

You have already released a bunch of ping pong balls beneath your ship, and you want to know how many of the balls actually contribute to the salvage. Fortunately, you know exactly where you have released the balls, and you have a very precise model of the ship. Can you compute how many of the balls are helping you out?

\includegraphics[width=0.70\textwidth ]{3-ship.jpg}
Figure 1: The shipwreck from Sample $2$. The fourth ping pong ball from the left, for instance, helps you out as it gets stuck between the anchor and the ship.

The sea is given as the $(x, y)$-plane. The surface of the sea is at $y=0$, so that the water is where the $y$-coordinate is less than or equal to zero. The shipwreck is modeled by a 2D polygon in this plane. The ping pong balls are modeled as points (floating points) which are released far below the shipwreck.

A ping pong ball floats straight upwards, unless it surfaces or it is blocked by an edge. If it can float upwards along an edge, it follows the edge. If it is blocked by a horizontal edge, or by a corner from which there is no edge going upwards, the ball is stuck.

A ball does not push the shipwreck up if it surfaces. If a ball gets trapped below the ship at $y=0$, it still contributes to pushing the ship up, and hence is counted in the final answer.


  • The input starts with a line with integers $3 \leq n \leq 10^3$, the number of vertices of the shipwreck, and $1 \leq b \leq 2\cdot 10^3$, the number of ping pong balls.

  • Then follow $n$ lines, each with two integers $-10^5\leq x, y \leq 10^5$, which give the vertices of the polygon in counter-clockwise order.

  • Then one line follows containing $b$ integers $x_1, x_2, \dots , x_ b$, indicating the $x$-coordinates where the ping pong balls were released. Each value satisfies $\lvert x_ i \rvert \leq 10^5$. The original $y$-coordinate of the ping pong balls is below $-10^5$.

The shipwreck is a simple polygon: its edges only intersect at vertices, and only two edges intersect at a vertex. Furthermore, no two $x$-coordinates, both of the points of the boat and of the balls, are the same.


  • The output consists of a single integer: the number of balls which end up pushing the shipwreck up.

Sample Input 1 Sample Output 1
4 4
1 2
4 -4
6 0
9 0
2 3 5 8
Sample Input 2 Sample Output 2
17 5
-28 2
-15 -5
-16 -4
2 -5
18 -1
21 -7
16 -7
22 -9
24 -8
26 -2
23 -6
20 0
28 2
0 2
1 15
-1 15
-2 2
-20 -10 10 19 25


  1. This does not work. Do not try this on your own sunken ship.
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in