ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Regional School Programming Contest 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Angry Birds

Time limit: 0.5 second
Memory limit: 64 MB
Problem illustration
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.


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 the minimum number of shots needed for hitting all the monkeys.


1 5
2 8
3 9
4 8
5 5
Problem Author: Fedor Fominykh
Problem Source: Ural Regional School Programming Contest 2011
To submit the solution for this problem go to the Problem set: 1875. Angry Birds