Kill the Pig
InterviewTime limit2sMemory limit256 MB
A bird flies along a parabola until the player taps, then continues along the tangent line; find the tap time so the path passes through the pig, or report Ok or Impossible.
- Level
Medium6 of 10
- Topics
- Geometry, Math, Binary search, Implementation
- Solved
- No attempts yet
Problem
In a certain computer game, the goal is to kill as many green pigs as possible by launching multicolored birds with different flight parameters from a slingshot.
This problem deals with a bird that has the following flight parameters. Right after launch it flies as a body thrown at an angle to the horizon would fly, along a parabola. However, after the player presses the screen or a mouse button, the bird accelerates so that from then on it flies essentially in a straight line. That line is tangent to the parabola at the point where the bird was at the moment the button was pressed.
We represent the screen as a plane with a coordinate grid and the origin at the bird's launch point. The launch parameters of the bird are given: α is the angle in degrees between the bird's initial velocity vector and the positive direction of the OX axis, V is the bird's speed in meters per second, g is the free-fall acceleration in meters per second squared, and X and Y are the coordinates of the pig in meters. You must determine at what moment the player should accelerate the bird so that it hits the pig. The pig and the bird are treated as points, and the free-fall acceleration is directed opposite to the OY axis. A hit means that the bird's flight trajectory crosses the vertical line through the point where the pig is located at a point no more than 10-4 meters away from the pig.
Input
The first line contains three integers: α, V, and g, the angle at which the bird is thrown, its initial speed, and the free-fall acceleration, respectively (0 < α < 90, 1 ≤ V, g ≤ 100).
The second line contains two integers X and Y, the coordinates of the point where the pig is located (0 ≤ X, Y ≤ 100). The pig is not at the origin.
Output
If there is no way to hit the pig, output the word Impossible.
If the pig can be hit without accelerating the bird, output the word Ok.
Otherwise, output a real number t, the amount of time in seconds that must pass from the bird's launch until it is accelerated.
If the pig can be hit both by accelerating the bird and without accelerating it, you may output either of these options.
When the answer is checked, a hit means that the bird's flight trajectory crosses the vertical line through the point where the pig is located at a point no more than 10-4 meters away from the pig.