ZOJ Problem Set - 3580
In the famous game Angry Birds, players can choose a direction to shoot a blue bird, which can be spilt into three birds to hit those annoying pigs or wood boards. Birds flies in parabola with gravity constant g=9.8m/s2.This time, Paopao is commanding her birds to break wood boards on the ground following these rules:
Apparently, some boards can be destroyed in the same time with one shoot. Paopao wants to know the least number of shoots she need to destroy all boards.
The problem contains multiple cases.
Each case starts with one integer and two real numbers indicating the number of boards n (1 ≤ n ≤ 16), the initial speed V (0 < V ≤ 1000), and Y (0 < Y ≤ 1000).
The following n lines each contains two real numbers x1, x2 (0 ≤ x1 < x2 ≤ 1000000), describing the cordinates of a board.
Process to the end of file.
For each test case, output the least number of shoots needed to eliminate all boards in a single line. If some board cannot be broken, output -1 instead.
2 1.0 1.0 0 0.0001 0.45 0.45001 3 1.0 1.0 0 0.0001 0.45 0.45001 0.5 0.6
Author: WAN, Xinyi
Contest: ZOJ Monthly, February 2012