BOXD - Boxdropper

no tags 

The University of Waterloo is famous for its booming population of geese, and many researchers go there to study them. One day, Doctor Y (known for his work in the field of boxology) decided to go there and investigate how good geese are at optimization problems.

At UW, there is a large lake (so large, in fact, that the boundaries are never an issue). Doctor Y decides to drop a number of 2D boxen onto this lake and command the geese to travel from one to another, recording how much time they spend flying as opposed to walking (naturally, the geese won’t swim, considering the not-so-appealing brown colour of the lake). He has a Boxdropper machine at his disposal to do the work for him – he can give it the following commands:

B $x_1$ $y_1$ $x_2$ $y_2$: Drop a box onto the lake such that its lower-left coordinate is at ($x_1$, $y_1$) and its upper-right coordinate is at ($x_2$, $y_2$). Doctor Y defines the origin to be somewhere in the middle of the lake. Note that boxen can overlap with one another.

G $a$ $b$: Command the geese to travel from the ath box dropped to the bth one, and record the total distance that they fly.

Since the scientific community has not yet realized the benefits of studying boxen, Doctor Y isn’t receiving much funding – as such, he only has $500$ boxen at his disposal, and his machine can only handle $10^6$ commands before it overheats.

The geese can walk across boxen freely, but sometimes they may have to fly over water to reach other boxen. The geese, secretly participating in the second stage of the Canadian Computing Competition every year, are well versed in optimization problems such as these, and so will always choose a path that will minimize the total distance that they spend flying. Given the commands that Doctor Y inputs into the Boxdropper, determine the distances recorded by it (one for every G command).

Input

On each line, one of the 2 types of commands will be given:

If the line starts with the character B, it will be followed by 4 integers ($x_1$, $y_1$, $x_2$, and $y_2$), each with absolute value no greater than $10^6$.

If the line starts with the character G, it will be followed by 2 integers ($a$ and $b$), with $a \neq b$ and $1 \leq a,b \leq n$ (where $n$ is the number of B commands inputted so far).

Commands should be read until EOF.

Output

For every G command, output the distance that the geese spend flying. The numbers should be printed one per line, and rounded off to 2 decimal places.

Example

Input:
B -1 2 1 5
B 3 -4 4 1
G 2 1
B 4 -3 6 -2
B 6 -6 8 -4
G 2 3
G 1 4

Output:
2.24
0.00
3.24

Explanation of Sample:

The lake looks like this:

For the first G command, the geese must fly along the red line, which has a length of √5.

For the second, the two boxen are touching, so no flight is necessary.

For the third, the geese must first fly along the red line, then walk across boxen 2 and 3, and finally fly along the blue line, which has a length of 1.

 


hide comments
Hasan Jaddouh: 2013-05-15 23:54:35

fixed my mistake but keep getting WA please give me some test cases.

submission ID: 9272370

RE: Your outputs are completely wrong, including some negative numbers - using %lf instead of %Lf when printing long doubles may have to do with it.

RE(hasan): thanks a lot :) got AC now

RE: Alright, no problem!

Last edit: 2013-05-16 16:41:08
Hasan Jaddouh: 2013-05-15 19:57:53

@Jacob Plachta, please tell me what's wrong with my solution 9271369

Edit: Oops, very big mistake!

Last edit: 2013-05-15 20:20:12

Added by:SourSpinach
Date:2013-05-07
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem