Problem D
Crazed Boar

A crazed boar has become lost in the forest! In its madness, it will charge in a random direction at blazing speed, until it has traveled a distance $d$, or until it hits a tree (in which case the boar will become dazed and end its charge), whichever comes first. Given the layout of trees around the boar, what is the probability the boar completes its wild charge without hitting a tree?

We will model the forest as the $xy$ plane, with the boar a disk of radius $b$ that begins centered at the origin $(0,0)$. We will also represent the trees as disks, with varying radii $r_ i$ and centers $(x_ i, y_ i)$. The boar charges by choosing a direction uniformly at random, and then translating in that direction for a distance $d$. The boar hits a tree and becomes dazed if, at any point during its charge, the boar’s body has nonzero area of overlap with any tree.


The first line of input contains a single integer $n$ $(0 \leq n \leq 10\, 000)$, the number of trees in the forest. $n$ lines follow, each of which contain three integers $x_ i$, $y_ i$, and $r_ i$, denoting the position and radius of the $i$th tree. These inputs satisfy $-10^6 \leq x_ i, y_ i \leq 10^6$ and $0 < r_ i \leq 10^6$. The final line of input contains two integer $b$ and $d$, the radius of the boar $(0 < b \leq 10^6)$ and the distance that the boar will charge $(0 \leq d \leq 10^6)$. You may assume that no tree overlaps with or touches the boar at the start of its charge (but trees might overlap or touch each other).


Print a single real number: the probability that the boar completes its charge without hitting any tree. Your answer will be considered correct if it has absolute or relative error at most $10^{-6}$.

Sample Input 1 Sample Output 1
3 0 1
1 4
Sample Input 2 Sample Output 2
6 0 3
0 6 3
-6 0 3
0 -6 3
1 3

Please log in to submit a solution to this problem

Log in