Problem E
Stretching Geometry
Input: Standard Input
Output: Standard Output
Time Limit: 2 Seconds
A square shaped garden is marked with
integer coordinates. The area of the garden is infinite. The lower left corner
of the garden is O (0,0) and the coordinate system is like normal
Cartesian coordinate system. A mad problem setter has planted (15001*15001) trees in 15001 rows and 15001 columns. So the
area where trees are planted is also a square. Trees are planted in a
coordinate (p,q) iff the following two conditions are
true:
a) d|p and d|q
b) p<=15000d and q<=15000d.
Here d is an arbitrary integer (0<d<11). In figure 1 below the value of d is 4.
The mad problem setter has drawn a 2D image of this garden, which looks somewhat like figure 1 but a lot larger. But the problem is that while
manipulating the image with a high precision imaging software he has stretched
the image b(b>0) times along x-axis and a(a>0) times along y- axis. For example Figure 2 is found by stretching figure-1, 3 times along x-axis and 2 times along y- axis. The trees in the pictures can be considered point
objects. So they remain point objects after any sort of stretching. Before or
after this stretching not all trees are visible from the origin O (0,0) due to some other trees, which are on the same line with
respect to O. In the above pictures the visible trees
are shown with red. You will be given the coordinate of one of the visible
trees in this stretched figure A (x1, y1). There will always be a tree at position B (x2, y2) in this stretched figure that is visible from O and whose angular distance φ from A with respect to O is minimum (I mean angle AOB is minimum) and in the positive direction (Counter
clockwise). Your job is to determine the coordinate of B (x2,y2). Of course, the mad problemsetter is looking for a very
efficient solution.
Input
For each line of
input except the last one produce one line of output which contains two
integers which are the values of x2 and y2.
152896
108 4 36 1.058827657765851e-6 43492
24 2 6 5.815846810938229e-7 -1 -1 -1 -1 1.000000000000000e-8 |
203856
144 54364
30 |
Problemsetter: Shahriar Manzoor, Member of Elite Problemsetters' Panel
“What makes these students outstanding? The answer is simple. They do! But, they can't do it alone. The ICPC community bands together universities, faculty, government and industry to create an environment where students set performance standards for each other. It is the willingness to challenge the norm and to take the challenge that sets these students apart. The ICPC community is set apart because the challenge is to become great problem solvers!”
-Bill & Marsha