d789: 00920 - Sunny Mountains
標籤 :
通過比率 : 72人/75人 ( 96% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-08-28 14:06

內容

Smith 夫婦到喜馬拉雅山去度蜜月。當太陽下山時,山頭的白雪被夕陽染成了紅色,這樣的景觀讓他們驚豔。

一般的人都會被這樣的景象所感動,但是 Smith 先生無法克服對數字的沈迷,他開始量測距離。這讓 Smith 太太很不開心。

問題

你需要幫 Smith 先生計算被夕陽染紅的山坡一共有幾公尺。他的蜜月就靠你了,你動作要快。

為了簡化問題,假設太陽下山時陽光 (Sunbeams)是水平的,地形則是以山巔及山坳的座標表示。如下圖 所示,地形是一連串的山巔及山坳,山巔及山坳會交錯出現。

圖中的向陽山坡 (Sunny mountain sides) 以粗線表示,地形的座標則以粗點表示。

這個問題便是要計算粗線的總長度。

請注意:(1) 對所有的座標 (x, y), 0 <= x <= 30000 and 0 <= y <= 8848;(2) 單位為公尺;(3) 所有的 X 座標卻互不相同;(4) 最左邊的點的 X 座標為 0,最右邊的點的 Y 座標為 0;(5) 座標總數 n <= 100。

輸入說明

輸入的第一行為 C (0 < C < 100 ),表示有幾筆測資。

每筆測資的第一行為座標數 N,接下來的 N 行為定義地形的座標,每行有兩個以空白隔開的整數 xy。第一個數字 x 為 X 座標,第二個數字 y 為 Y 座標。

輸出說明

每筆測資請輸出一行,每行有一個含有兩位小數的實數。這個實數表該筆測資的向陽山坡的總長度。

範例輸入
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
範例輸出
1446.34
1414.21
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
提示 :
標籤:
出處:
UVa920 [管理者:
snail (蝸牛)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」