Watch the Marathon
Time limit8sMemory limit1024 MB
Given a segment from the origin to (a, b), find the integer lattice point off the segment closest to it, breaking ties by smallest X, then smallest Y.
- Level
Medium6 of 10
- Topics
- Number theory, Geometry
- Solved
- No attempts yet
Problem
You are a track and field fan and decide to watch a marathon in person. In this race, the course is the line segment connecting the origin on the plane and the point . Because of traffic control during the race, you can watch only from points whose and coordinates are both integers and that are not on the course.
You want to watch from as close to the course as possible. Among the points that satisfy the conditions above, find the point with the smallest Euclidean distance to the course. If several points tie, output the one with the smallest coordinate. If there is still a tie, output the one with the smallest coordinate.
Input
The input consists of at most datasets. Each dataset is given in this format:
and are integers from to , inclusive, and give the coordinates of one endpoint of the marathon course.
The input ends with a line containing two zeros.
Output
For each dataset, print the and coordinates of the best point to watch the race, separated by a space, on one line.