시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 256 MB | 2 | 2 | 2 | 100.000% |
Pasha has entered a desert navigation contest, <<World Sensei of Orienteering 2018>> (WSO 2018). The desert can be viewed as an endless plane. The desert has been prepared for the contest, with $n$ checkpoints numbered, in numerical order, from $1$ to $n$, the $i$th checkpoint having the coordinates ($x_{i}$, $y_{i}$).
The contest rules are the following:
Pasha is in the dark on which checkpoints $s$ and $f$ will be chosen by the organizing committee, so he needs to know the mean value of the number of penalty points needed. Being a true professional, he always choses the route which needs the minimal number of penalty points. All possible variants of $s$ and $f$ should be considered equiprobable.
Write a program that will help Pasha determine the mean value.
The first line of the input data contains two integers $n$ and $v$ --- the number of checkpoints and gas tank capacity, respectively ($2 \leqslant n \leqslant 200$, $1 \leqslant v \leqslant 10^{5}$).
Each of the next $n$ lines contains a checkpoint with three integers $x_{i}$, $y_{i}$ and $p_{i}$ --- the coordinates of the checkpoint and the number of penalty points for a liter of fuel at it, respectively ($-10^{4} \leqslant x_{i}, y_{i} \leqslant 10^{4}$, $1 \leqslant p_{i} \leqslant 10^{6}$). No two checkpoints are the same.
It is guaranteed that the capacity of the gas tank is enough to reach any checkpoint from any other checkpoint, possibly refuelling on the way.
The only line of the output data must contain a single real number --- the number of penalty points required on average. The answer will be considered correct when its absolute or relative error is less than $10^{-6}$.
5 3 0 0 3 0 2 2 1 1 5 3 1 2 2 2 4
6.634062043
3 100000 0 0 1000 1 1 1 2 0 1000
943.751850623645282
There are only 20 variants of the start and final checkpoints in the first example. In all but four variants, the optimal route consists in buying the necessary volume of gas at the first checkpoint and proceeding directly to the end point.
In the case of driving from (0, 2) to (3, 1) or back, it is impossible to take a direct drive because of the insufficient tank capacity. The optimal variant is to fill the tank maximally at the starting point and driving through the checkpoint (2, 2), adding some fuel there. The total penalty in this case will be $2 \cdot 3 + 4 \cdot (\sqrt{2} - 1)$.
Similarly, in case of going from (0, 0) to (3, 1) and back, the optimal solution is to drive through the checkpoint (1, 1) for a refill.
In the second example it is sometimes worth to drive through the intermediate checkpoint to buy fuel there, even though gas tank is large enough to sustain a direct route.