Doug’s game studio is working on a tactical military game in which players carry out aerial bombardments against an island nation controlled by an evil despot. The island is defended by surface-to-air missile batteries (SAMs) that are strategically placed along the shoreline. Fortunately for the players, the island’s defense budget has been recently slashed, and there are undefended gaps throughout the shoreline that are outside the range of any SAM.
To keep the game fun, players can respawn in a new aircraft at various offshore points whenever they get shot down. Doug wants to give newly respawned players a fighting chance by ensuring that their spawn points are
outside the range of any SAM, and
no more than a certain straight-line distance from the nearest undefended point on the shoreline.
This ensures that new respawns can get back into the action relatively quickly, without the threat of being shot down again immediately.
The island’s landmass is represented in the game as a polygon in 2D space. Certain vertices of the polygon contain SAMs, each of which can fire in a radius $r_ i$ around itself. Given the layout of the island and its defenses, help Doug determine if a certain spawn point is valid according to the rules above.
The input begins with a single line containing an integer $n$ ($3 \le n \le 100$), and a real value $d$ ($1.0 \le d \le 50.0$), separated by a space. $n$ is the number of vertices in the polygon comprising the island’s landmass, and $d$ is the maximum allowable straight-line distance from a valid spawn point to the nearest undefended point on the shoreline.
The next $n$ lines each represent a vertex $V_ i$ of the polygon, $1 \le i \le n$. Each of these lines begins with two space-separated real values $x_ i$ and $y_ i$ ($-100.0 \le x_ i, y_ i \le 100.0$), indicating the Cartesian coordinates of $V_ i$. They may also be followed by a third space-separated real value $r_ i > 0$, indicating the firing radius of the SAM battery located at $V_ i$. The absence of $r_ i$ indicates that $V_ i$ does not contain any defenses.
Finally, the last line of input contains two space-separated real values $x_ s$ and $y_ s$ ($-150.0 \le x_ s, y_ s \le 150.0$), indicating the Cartesian coordinates of a potential offshore respawn point.
The vertices $V_ i$ are provided in order such that $\{ V_1V_2, V_2V_3, V_3V_4, \ldots , V_{n-1}V_ n, V_ nV_1\} $ is the set of edges of the polygon, and no consecutive edges are collinear. There is guaranteed to be a nonzero length of undefended shoreline on every edge, and the firing range of each SAM battery intersects only its two adjacent edges and no other edges.
The point $(x_ s, y_ s)$ is guaranteed to be outside of the polygon, and $(x_ s, y_ s)$ is always at least $0.001$ away from the shoreline and from any firing range circumferences. Furthermore, the distance from $(x_ s, y_ s)$ to the nearest undefended point on the shoreline differs from $d$ by at least $0.001$. All real values are specified with at most $6$ digits after the decimal point.
Output a single line containing yes if the potential spawn point is valid, or no if not.
Sample Input 1 | Sample Output 1 |
---|---|
3 2.0 2 2 1 0 0 2 -2 1 3.99 0 |
yes |
Sample Input 2 | Sample Output 2 |
---|---|
3 2.0 2 2 1 0 0 2 -2 1 4.01 0 |
no |
Sample Input 3 | Sample Output 3 |
---|---|
3 2.0 2 2 1 0 0 2 -2 1 1.5 -2 |
no |