Overlapping Maps

Time limit1sMemory limit128 MB

Summary
Given a smaller rotated, scaled map lying inside a larger one, find the unique point that represents the same location on both maps.
Level

Medium4 of 10

Topics
Geometry, Math, Implementation, Binary search
Solved
No attempts yet

Problem

Fred and Sam are traveling together. Both have maps of the same area. The two maps cover exactly the same territory and have exactly the same width-to-height ratio, but Sam's map is drawn at a smaller scale than Fred's, so it is a bit smaller.

Fred lays his map flat on a table. Sam tosses his map on top of it. The smaller map ends up offset and rotated, yet it still lies entirely on top of the larger map. Fred pushes a pin through the smaller map, and the pin goes all the way down to the larger map. Sam is amazed: “Wow! The spot that pin marks is the same place on both maps!” Fred replies: “It's not so amazing — there must always be exactly one such point.”

Given the size of the larger map and the offset, scale, and rotation of the smaller map (which lies entirely on top of the larger map), find the single point that marks the same place on both maps.

Input

The input contains several test cases. Each test case is a single line with six integers:

w h x y s r
  • ww and hh (0<w,h≤10000 < w, h \le 1000) are the width and height of the larger map. The larger map lies on a plane with its southwest corner at the origin, its northwest corner at (0,h)(0, h), its southeast corner at (w,0)(w, 0), and its northeast corner at (w,h)(w, h).
  • xx and yy (0≤x≤w0 \le x \le w, 0≤y≤h0 \le y \le h) are the plane coordinates of the southwest corner of the smaller map.
  • ss (0<s<1000 < s < 100) is the scale of the smaller map as a percentage of the larger map (s=50s = 50 means the smaller map has half the width and half the height of the larger map).
  • rr (0≤r<3600 \le r < 360) is the angle, in degrees, of counter-clockwise rotation of the smaller map about its southwest corner (r=90r = 90 means the southeast corner is rotated to point due north of the southwest corner).

The smaller map is guaranteed to lie completely within the borders of the larger map. The input ends with a line containing six zeros, which is not processed.

Output

For each test case, output two real numbers xx and yy: the coordinates of the point that marks the same place on both maps. Print each number rounded to exactly two decimal places, separated by a single space. Do not print any extra spaces, and do not print blank lines between test cases.

Examples3

  1. Example 1

    Input
    100 100 50 50 25 0
    100 100 50 50 25 45
    0 0 0 0 0 0
    
    Expected output
    66.67 66.67
    45.59 70.53
    
  2. Example 2

    Input
    200 100 20 10 40 0
    0 0 0 0 0 0
    
    Expected output
    33.33 16.67
    
  3. Example 3

    Input
    100 100 60 20 30 90
    0 0 0 0 0 0
    
    Expected output
    49.54 34.86