Programming Problem #19
"Integral Lines"
Consider an equation in the real variables x and y of the form
Ax+By=C, where A, B and C are integers. Its graph is a straight line provided
that either A or B is nonzero. Some of the points on such a line may have
integral coordinates; for example, the point (3,4) is on the line defined by
the equation 3x+2y=17. Let S be the set of all points (x,y) on the
line such that:
- x and y are both integers, and
- the absolute values of x and y are less than 32768.
Your job is to find all of the points in S whose distance from the origin is
minimal.
The input consists of one or more lines, each of which contains the integer
coefficients A, B, and C, separated by a space. The absolute value of
every coefficient will be less than 32768. For each equation, output the
specified points as shown in the example.
If there are no such points, output the single word 'NONE'.
Input must be read from the file "prob19.in",
and output must be written to the file "prob19.out".
All output to the screen will be ignored.
Example Input
<BOF>
1 1 2
6 15 8
-3 1 15
<EOF>
Example Output
(1,1)
NONE
(-4,3) (-5,0)
A version of this problem originally appeared in the 1989 Pacific regionals.
Dr. Eric Shade