2011年12月17日 星期六

920 - Sunny Mountains

下圖為群山被陽光照射的示意圖,被陽光照射到地方以紅線表示,本題請你計算所有被照射到的長度。為了簡化問題,我們假設陽光與地面平行,並給定山峰與山谷的位置。
位置以(x, y)表示,且 0 <= x <= 30000, 0 <= y <= 8848,最左邊的點其x=0,最右邊的點其y=0,所有點的數量 n <= 100。

Input

輸入資料的第一列有一個整數 C (0 < C < 100)表示測試資料的組數。
每組測試資料的第一列為整數N,表示有N個點,接下來有N個點的位置(x, y),分別表示山峰或山谷。

Output

請對每組測試資料輸出上圖中紅色線段的總長度為何,請輸出到小數點後兩位。

Sample Input

2
11
1100 1200
0 500
1400 100
600 600
2800 0
400 1100
1700 600
1500 800
2100 300
1800 700
2400 500
2
0 1000
1000 0

Sample Output

1446.34
1414.21

原文出處

沒有留言:

張貼留言