回分類題庫
g052: A.樹上的松鼠
關鍵字: NPSC 2009 國中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 123 Times / 120 Users | Submit : 185 Times / 125 Users | Accepted rate : 96%
題目加入時間 : 2011-12-26 14:58

Content: 简体中文

世界上有很多棵樹,每棵樹長在不一樣的地方,有著不一樣的樹幹和樹枝。有一群松鼠住在一片樹林中,他們喜歡爬樹,喜歡爬到高的地方。

今天,松鼠王想要爬到最高的地方,眺望遠方的草地,並尋找他們的食物松果。不過,松鼠王的數學不太好,他知道這些樹的形狀,可是不知道最高的地方在哪裡。你能幫忙他嗎?

在松鼠王的認知中,樹幹和樹枝都是一條直線。樹幹的底端一定在地表,頂端則會在半空中。樹枝的一端會接在樹幹或其他樹枝的中間,另一端也會在半空中。樹枝有分粗細,比較粗的樹枝不能接在比較細的樹枝中間。

現在松鼠王給你一張地圖,並告訴你每個樹幹和樹枝的位置,請你找出這片樹林中最高的位置。

Input:

第一行有一個整數 T,代表後面有幾筆測試資料。接下來有 T 組測試資料,每一組的第一行有一個整數 N,表示有這片樹林中有幾個樹幹和樹枝。再來有 N 行,每一行代表一個樹幹或樹枝。每個樹幹和樹枝都是用

x1 y1 h1 x2 y2 h2

表示,代表它兩端的位置。(x1, y1) 和 (x2, y2) 代表這兩個端點在地圖上的位置,而 h1 和 h2 代表這兩個端點的高度。
題目保證每組測試資料至少會有一個樹幹,並且樹幹和樹枝都會適當地連接。還有,輸入的每個數字都是整數, 0<N<=1000,0<xi、yi<=10000,0<h<=10000 。

Output:

對每一筆測試資料輸出一個整數,代表這片樹林中松鼠王所能到達的最高位置的高度。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
2
5 5 0 5 5 6
5 5 5 7 7 7
3
5 5 0 5 5 6
5 5 5 6 6 8
5 5 3 3 3 3

Sample Output :

7
8

Hint :

Author :

NPSC 2009 國中組初賽 (管理員:sagit)

  Solve it!   Status Forum