Unsatisfied with the usual Santa-tracking tools, Wesley has decided to make one of his own, called SantaTracker++!
Santa's entire trip can be modelled on the Cartesian plane. Santa's sleigh travels at a constant speed from
Tracking Santa's movement is too unpredictable, so instead SantaTracker++ needs to predict which house he is currently located at. One known fact about Santa is that he will always deliver gifts to the house that is closest to his sleigh's position on the voyage interval. A house is considered to be closest if there is at least one point on the rectangle closer to the sleigh's current position than any other rectangle in Euclidean distance. In case of a tie in distance the house with the smaller index will be considered closer (these houses are more likely to house well-behaved kids).
For undisclosed reasons, Wesley needs to know which houses will Santa most likely end up at any point in the journey. For every house, find the percentage of Santa's trajectory where Santa's sleigh is closest to that house. As the lead developer of SantaTracker++, please help him out!
Constraints
For this problem, you will NOT be required to pass all the samples to receive points, and you are NOT required to pass all previous subtasks to receive points for a specific subtask.
For all subtasks:
Subtask 1 [8%]
Subtask 2 [18%]
Subtask 3 [33%]
Subtask 4 [41%]
No additional constraints.
Input Specification
The first line will contain two integers
The next
Output Specification
This problem is graded with a custom checker.
Output \n
character and has no leading nor trailing spaces.
Your answer will be considered correct if it has an absolute or relative error of at most
Sample Input 1
2 10
1 2 5 1
2 1 1 5
Sample Output 1
52.679491924
47.320508076
Sample Explanation 1
The sleigh will be closest to the first house for
Sample Input 2
4 7
1 3 0 0
3 4 0 0
5 5 0 0
3 4 0 0
Sample Output 2
53.571428571
35.714285714
10.714285714
0.000000000
Comments