WIJGT - Will Indiana Jones Get There


Documento sin título

Indiana Jones is in a deserted city, annihilated during a war. Roofs of all houses have been destroyed and only portions of walls are still standing. The ground is so full of mines that the only safe way to move around the city is walking over the remaining walls. The mission of our hero is to save a person who is trapped in the city. In order to move between two walls which are not connected Indiana Jones thought of taking with him a wooden board which he could place between the two walls and then cross from one to the other.

Initial positions of Indiana Jones and the trapped person are both on some section of the walls. Besides, walls are either in the direction South-North or West-East. You will be given a map of the city remains. Your mission is to determine the minimum length of the wooden board Indiana Jones needs to carry in order to get to the trapped person.

Input
Your program should process several test cases. Each test case starts with an integer N indicating the number of wall sections remaining in the city (2 <= N <= 1000). Each of the next N lines describes a wall section. The first wall section to appear is the section where Indiana Jones stands at the beginning. The second section to appear is the section where the trapped person stands. Each wall section description consists of three integers X , Y and L (–10000 <= X , Y , L <= 10000), where X an Y define either the southernmost point of a wall section (for South-North sections) or the westernmost point
(for West-East wall sections). The value of L determines the length and direction of the wall: if L > 0, the section is West-East, with length L ; if L< 0, the section is North-South, with length | L | . The end of input is indicated by N = 0.

Output
For each test case in the input your program should produce one line of output, containing a real value representing the length of the wooden board Indiana Jones must carry. The length must be printed as a real number with two-digit precision, and the last decimal digit must be rounded. The input will not contain test cases where differences in rounding are significant.

Sample input
14
1 1 5
6 8 2
7 2 -2
5 3 3
2 5 2
2 3 2
2 3 -2
4 3 -2
0 7 1
1 8 2
3 6 -2
4 7 2
6 6 1
6 6 -2
3
-10 0 20
-5 1 10
50 50 100
0

Output for the sample input
1.41
1.00


hide comments
humble_coder: 2014-10-05 22:01:22

if L = 0 does it indicate that the cordinate is only a point??

Petar Bosnjak: 2014-07-26 22:09:49

I have really enjoyed solving this task!

Josef Ziegler: 2009-11-20 17:48:35

Don't forget:
L can also get 0

Last edit: 2009-11-20 17:48:59

Added by:Andrés Leonardo Rojas Duarte
Date:2007-07-25
Time limit:2.857s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:ACM International Collegiate Programming Contest 2002 – South America