At the Petrozavodsk Training Camp, the Psych Up team didn't waste any
time. The programmers passed with three stars all the levels of the
popular game “Angry Birds Rio” except for one level. Whatever they tried
to do, it didn't work. Then the programmers decided to automate the
process and sat down at their computer.
The game goes as follows. There is a slingshot shooting with angry birds
at the left bottom corner of the map. The slingshot can shoot a bird at
any angle to the ground. The aim is to hit monkeys suspended in the air to
the right of the slingshot. No forces act on the birds except for the
gravity force, which imparts to them an acceleration of g = 9.81 m/s2
directed downward. As a result, the horizontal component of the velocity
of each bird is constant, while the vertical component changes with time.
The programmers can't pass a level at which there are only five monkeys
and the slingshot. It is required to defeat all the monkeys with the
minimum number of shots. Hitting a monkey doesn't affect a bird in any
way, so its motion is continued. The birds and monkeys are so small that
they can be regarded as points. The map of the level is infinite to the
right and upward.
Input
In each of the five input lines you are given a pair of integers not
exceeding 10 000, which are the coordinates of a monkey in meters. The
slingshot is at the point (0, 0). The Ox axis is directed to the right
and the Oy axis is directed upward. It is guaranteed that there is no
straight line containing the slingshot and more than one monkey.
Output
Output the minimum number of shots needed for hitting all the monkeys.
Sample
input | output |
---|
1 5
2 8
3 9
4 8
5 5
| 1
|
Problem Author: Fedor Fominykh
Problem Source: Ural Regional School Programming Contest 2011