Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Will Indiana Jones Get There?
Time Limit: 1000MSMemory Limit: 10000K
Total Submissions: 2132Accepted: 551

Description

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

Sample Output

1.41
1.00

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator