b421: 01077 - The Sky is the Limit 強化
標籤 :
通過比率 : 38% (3 人 / 8 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2015-06-30 06:38

內容

Banff 市找一家廣告商宣傳旅遊,計畫的口號「讓城市周圍的山脈的天際線 (skyline) 成為加拿大最壯麗的」但加拿大消費者保護組織 (ICPC) 認為「最壯麗的天際線」一詞非常主觀、很容易受到誤導,因此廣告商打著「Banff 加拿大最長天際線」企圖要從 ICPC 手中拿到廣告核准。

你的工作就是要找到天際線總長,每一座山脈是由一個等腰三角形構成,而天際線由數個山脈的輪廓構成,天際線總長為山脈的輪廓加總,隱沒到另一座山脈之後的輪廓線是不予計算,同時水平部分因不是山脈也不予計算。

如下圖,只有粗線的部分才算天際線。

輸入說明

輸入有多組測資,每一組測資第一行會有一個整數 $N$,$N$ 表示有多少座山脈。接著會有 $N$ 行,每一行上會有三個整數 $X, H, B$,分別表示山頂的中心座標在水平位置上的座標值、山脈的垂直高度、山脈的水平寬度。

  •  $0 < N \le 10000$
  • $ 0 <X < 1000000$
  • $ 0 < H, B < 32767$

最後一組測資以 $N = 0$ 為程序結束。

輸出說明
每一組測資輸出兩行,第一行表示輸出天際線長度,採用四捨五入到整數位,接著是一個空行,請參考範例輸出。
範例輸入
1 
100 50 100
2
100 50 100 
100 50 100
3 
20 30 35 
37 24 29 
60 20 13 
0
範例輸出
Case 1: 141

Case 2: 141

Case 3: 138

測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 1.0s , <1M
公開 測資點#1 (10%): 5.0s , <1M
公開 測資點#2 (10%): 5.0s , <1M
公開 測資點#3 (10%): 5.0s , <1M
公開 測資點#4 (30%): 5.0s , <1M
公開 測資點#5 (30%): 5.0s , <1M
提示 :
大測資中,沒入在另一座山脈的情況會很少。
標籤:
出處:
UVa1077 [編輯:
morris1028 (碼畜)
]


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