Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3580
Angry Birds

Time Limit: 4 Seconds      Memory Limit: 65536 KB

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:

  • Birds are shooted in the starting position (0,Y).
  • Birds' initial speed is fixed as V. However, her direction can be arbitrarily determined by Paopao.
  • Each Bird can be spilt into three birds in the starting position. Assuming the angle of the orign direction vector is p, the angles after spilting is p-pi/12, p, and p+pi/12(in Radian). Three birds share the same initial speed V. Notice that there is a ceiling with y=Y, that is to say, any birds flying above the starting position will disappear instantly.
  • Wood boards are placed on the ground (the y-axis of ground is 0). The thickness of each board can be ignored and each board can be regarded as a simple line with cordinates (x1,0)-(x2,0). Once hit by a bird, the board will disappear. Hitting on the boundary of the board won't break the board and no boards will overlap each other.

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.

Sample Input

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

Sample Output


Author: WAN, Xinyi
Contest: ZOJ Monthly, February 2012
Submit    Status