This page is still under construction.

Parts of this page are still being built. What you see may change.

Return of Space Turtle

Interview

Time limit1sMemory limit128 MB

Summary
Two objects travel closed rectangular paths on a grid; find the minimum distance between them, sampled once per minute at integer times.
Level

Medium6 of 10

Topics
Simulation, Math, Implementation, Brute force
Solved
No attempts yet

Problem

Remember Space Turtle, the fearless space adventurer? When we last met him, he was searching for the fabled Golden Shell aboard the Tortoise, his trusty spaceship.

Space Turtle has run out of fuel, but he believes he is very close to the Golden Shell. Unfortunately, because of a spatial anomaly (the kind you see on TV), both the Tortoise and the Golden Shell are trapped on a two-dimensional grid, endlessly travelling along very strange orbits. Each orbit moves from one lattice point (a point with integer coordinates) to an adjacent lattice point, and travelling one unit of distance takes exactly one minute. The Tortoise and the Golden Shell entered the anomaly at the same instant, so you can think of this simply as two objects moving around on a grid.

As the Tortoise and the Golden Shell travel along their orbits, the distance between them changes a great deal. As the lonely keeper of the Golden Shell, your job is to observe the Tortoise once every minute — precisely when both you and the Tortoise are on lattice points — and record how far away it is. Your goal is to determine the closest distance at which the Tortoise is ever observed from the Golden Shell. (It may come closer while you are not looking, but that does not count.)

Input

The first line contains three integers sxs_x, sys_y, and sms_m: the coordinates (sx,sy)(s_x, s_y) of the Tortoise's starting point and the number of moves sms_m in its orbit. Each of the next sms_m lines describes one move as an integer dd (−100≤d≤100-100 \le d \le 100) and a letter cc, separated by a space. The value dd is the signed distance the Tortoise moves, and cc is the direction, either X or Y, corresponding to the xx- and yy-axes of the grid. There are at most 100100 move lines.

After this orbit comes an analogous description of the Golden Shell's orbit: a line with txt_x, tyt_y, and tmt_m, followed by tmt_m move lines in the same format. Both orbits are guaranteed to return to their starting point, so each one is a closed cycle.

Output

Output the closest distance ever observed between the Tortoise and the Golden Shell, rounded to 22 decimal places. If the two ever meet on the same lattice point, output 0.00.

Examples3

  1. Example 1

    Input
    0 0 4
    -1 Y
    -1 X
    1 Y
    1 X
    1 0 4
    -1 X
    1 Y
    1 X
    -1 Y
    
    Expected output
    1.00
    
  2. Example 2

    Input
    0 0 4
    1 X
    1 Y
    -1 X
    -1 Y
    2 2 4
    -1 X
    -1 Y
    1 X
    1 Y
    
    Expected output
    0.00
    
  3. Example 3

    Input
    0 0 0
    3 4 0
    
    Expected output
    5.00