ZOJ Problem Set - 3589
Because of the 10th anniversary of ZOJ, Dai decides to write a beautiful song as the present. What's more, to let more people enjoy the anniversary, he is going to make a beatmap for the song in a famous music game - osu!.
osu! is a rhythm-cliking music game.
When you are playing osu!, some notes will appear on the screen. Each notes has a postion (x,y). The only thing you need to do is to click them with the rhythm. So it's impossible that two notes appear at the same time - Your mouse can't divide into two parts, can it?
A beatmap is a file that storaged all information of notes. After several days, Dai finished his work - He made a wonderful beatmap for the special song! However, to make the beatmap being admitted to all people, he need to calculate the difficulty of the beatmap. How to calculate the difficulty? First of all, we need to rearrange the notes by time and divide them into k consecutive parts. For example, if there are some notes appear at time 1, time 2, time 4, time 5, and k is 2, a vaild dividing plan is (1,2), (4,5). Of course, (1), (2,4,5) is also vaild.
And we define the distance of neighbour parts is the distance of the last note of previous part and the first note of next part. As below, the distance of (1) and (2,4,5) is the distance of note 1 and 2. Finally, the difficulty of a beatmap is the minimum distance of all distances of neighbour parts.
Dai knows that the difficulty is different if he divides the beatmap in different ways. So please tell him what's the maximum difficulty he can get.
The input contains several test cases.
For each test case, the first line is a string "[HitObjects]", which means the beginning of a test case. The second line is a number k (1 ≤ k ≤ the number of notes), which means the beatmap need to cut into k parts.
Then followed several lines, each line has the same formula [x],[y],[Time],[NewCombo],[Sound] (0 ≤ x,y ≤ 1000, 0 ≤ Time ≤ 231-1, 0 ≤ NewCombo ≤ 1, 0 ≤ Sound ≤ 100). The number of notes will not exceed 100001 (105+1) and all values in this formula are integers. There's no empty line between the test cases. Process to END_OF_FILE.
By the way, you can find informations about NewCombo and Sound here: http://en.wikipedia.org/wiki/Osu!.
For each test case, output a real number as the description required. The number should rounded to 3 digits after the decimal point.
[HitObjects] 1 100,100,1,0,2 100,100,2,0,2 100,100,3,0,2 [HitObjects] 2 100,100,1,0,2 100,100,2,0,2 100,100,3,0,2
Author: DAI, Longao
Contest: ZOJ 10th Anniversary Contest