| Codeforces Round 357 (Div. 2) |
|---|
| Закончено |
Дима живёт в общежитии, а вместе с ним в комнате живут тараканы.
В момент времени 0 Дима увидел ползущего по столу таракана и сразу захотел его убить. Диме нужно ровно T секунд, чтобы прицелиться, после чего точным ударом он убьёт ползущее насекомое.
Чтобы выжить, таракану нужно за T секунд успеть забежать в тень, которую отбрасывают стоящие на столе тарелки. Тень, отбрасываемая каждой из тарелок, имеет форму круга, при этом круги тени, отбрасываемые разными тарелками, могут пересекаться и вкладываться друг в друга произвольным образом.
Таракан поступает так: он равновероятно выбирает направление движения, после чего бежит по прямой в выбранном направлении с постоянной скоростью v. Если в некоторый момент времени t ≤ T таракан оказывается в тени, то он останавливается и выживает, в противном случае Дима успевает прицелиться и уничтожить его точным ударом. Считайте, что точный удар Димы происходит мгновенно.
Определите вероятность того, что таракан выживет.
В первой строке входных данных записаны четыре целых числа x0, y0, v, T (|x0|, |y0| ≤ 109, 0 ≤ v, T ≤ 109) — координаты таракана в декартовой системе координат в момент времени 0, его скорость и время прицеливания Димы соответственно.
В следующей строке дано целое число n (1 ≤ n ≤ 100 000) — количество кругов тени, отбрасываемых тарелками на стол.
В следующих n строках даны описания кругов тени. В i-й из этих строк даны три целых числа xi, yi, ri (|xi|, |yi| ≤ 109, 0 ≤ r ≤ 109) — координаты центра i-го круга тени в декартовой системе координат и его радиус соответственно.
Считайте, что стол достаточно большой для того, чтобы таракан не успел добежать до его края и избежать точного удара Димы.
Выведите единственное вещественное число p — вероятность того, что таракан выживет.
Ответ будет засчитан, если его относительная или абсолютная погрешность не превысит 10 - 4.
0 0 1 1
3
1 1 1
-1 -1 1
-2 2 1
0.50000000000
0 0 1 0
1
1 0 1
1.00000000000
Первый пример можно изобразить так:
Красным цветом окрашены зоны, выбрав точку в которых в качестве направления движения, таракан будет убит, зеленым же окрашены зоны, выбор точек в которых в качестве направления позволяют таракану выжить. Заметьте, что зона, содержащая круг с центром в точке ( - 2, 2), окрашена в красный, так как таракан не успевает добежать до этого круга за одну секунду.
