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 行為定義地形的座標,每行有兩個以空白隔開的整數 x 及 y。第一個數字 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
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|