Honed Hops
Time limit1sMemory limit128 MB
Given two sets of sampled points on a nonnegative quadratic jump arc, decide whether they necessarily come from the same parabola, cannot, or it is undecidable.
- Level
Medium6 of 10
- Topics
- Math, Geometry, Implementation
- Solved
- No attempts yet
Problem
In the Olympics, appearances do matter!
A long jumper's trajectory gives the height at horizontal position as , where is a quadratic describing a downward-opening parabola whose vertex lies in the upper half-plane. That is, and .
Thanks to rigorous training, each jumper always jumps with the same trajectory, and because of corporate sponsorship and branding requirements no two jumpers share the same trajectory.
Adoring fans who want to preserve the moment occasionally sample their favorite athlete's coordinates at various times and write them down, such as . Given two sample sets, determine whether they were taken from the same athlete.
Input
The input contains multiple test cases, each separated by a blank line. Each test case consists of three lines.
The first line contains two integers and () separated by a space, giving the number of sample points in the first and second sample sets, respectively.
The second and third lines contain the sample points of each set in the format . Every coordinate is an integer, , and for each , and . Be careful that your calculations have sufficient precision for all input within these bounds.
Input is terminated by a single line containing 0 0; do not process that line.
Output
For each test case, output a single line: same if the two sample sets are definitely from the same athlete, different if they are definitely from different athletes, and unsure if there is not enough information to tell.