題目 1964:
藍(lán)橋杯算法提高VIP-Contour Mapping
時間限制: 2s
內(nèi)存限制: 192MB 提交: 5 解決: 0
題目描述
等高線圖可以描繪一個區(qū)域的地勢。等高線圖上的等高線代表等高海拔。比如，一張等高線圖上可能有一條線代表海拔100米的區(qū)域，另一條代表海拔200米的區(qū)域等等。
等高線圖繪制協(xié)會（Association for Contour Mapping，簡稱ACM）需要程序讀取從衛(wèi)星獲取的海拔信息并繪制等高線圖。ACM尤其關(guān)注每張地圖上所有等高線的長度之和。海拔信息的形式為一個整數(shù)序列，依次代表在一條從西往東的掃描線上取的等距離的點的海拔。掃描線間距的取值使得測量區(qū)域內(nèi)所有不在邊緣的每個測高點都有6個其他的測高點離它最近，而且相互等距（這里忽視海拔高度），如圖1和圖2所示。
ACM的做法是，用線段連接每個點與距其最近的所有點，構(gòu)造出許多三角形，并用這些三角形來估計實際地形。每個三角形會被視為一個平面，由其三個頂點的坐標(biāo)和海拔確定。如果把三角形投影到海平面上，這些三角形會是等邊三角形。
在上圖中，黑色的數(shù)字代表海拔信息，紅色虛線和數(shù)字代表等高線。圖1中有一條海拔為5的等高線。圖2中在海拔為6和9之處分別有一條等高線。等高線可以穿過三角形的內(nèi)部或者緊貼三角形的一邊。
由于測高點的特殊選取方式，編號為偶數(shù)的掃描線較之于編號為奇數(shù)的掃描線上會多取一個測高點。圖中最上面的一條線是第一條掃描線。
等高線圖繪制協(xié)會（Association for Contour Mapping，簡稱ACM）需要程序讀取從衛(wèi)星獲取的海拔信息并繪制等高線圖。ACM尤其關(guān)注每張地圖上所有等高線的長度之和。海拔信息的形式為一個整數(shù)序列，依次代表在一條從西往東的掃描線上取的等距離的點的海拔。掃描線間距的取值使得測量區(qū)域內(nèi)所有不在邊緣的每個測高點都有6個其他的測高點離它最近，而且相互等距（這里忽視海拔高度），如圖1和圖2所示。
ACM的做法是，用線段連接每個點與距其最近的所有點，構(gòu)造出許多三角形，并用這些三角形來估計實際地形。每個三角形會被視為一個平面，由其三個頂點的坐標(biāo)和海拔確定。如果把三角形投影到海平面上，這些三角形會是等邊三角形。
在上圖中，黑色的數(shù)字代表海拔信息，紅色虛線和數(shù)字代表等高線。圖1中有一條海拔為5的等高線。圖2中在海拔為6和9之處分別有一條等高線。等高線可以穿過三角形的內(nèi)部或者緊貼三角形的一邊。
由于測高點的特殊選取方式，編號為偶數(shù)的掃描線較之于編號為奇數(shù)的掃描線上會多取一個測高點。圖中最上面的一條線是第一條掃描線。
輸入格式
輸入第一行有4個整數(shù)s、p、d和h。
s代表掃描線的條數(shù)。
p代表編號為奇數(shù)的掃描線上的測高點數(shù)，編號為偶數(shù)的掃描線上有p+1個測高點。
d代表無視海拔時，每個測高點與距其最近的測高點的距離（即三角形的邊長）。
h代表等高線的海拔間隔。在最后的等高線圖中，在所有海拔為h的整數(shù)倍的地方都會有一條等高線。注意一張地圖上同一海拔的等高線可能有多條。當(dāng)一整塊區(qū)域水平時，只在邊界處有等高線（見圖2中海拔為9的等高線）。
接下來共s行，每行描述一條掃描線。對于奇數(shù)行，每行含有p個整數(shù)，從左到右表示掃描線上測高點的數(shù)據(jù)。對于偶數(shù)行，每行含有p+1個整數(shù)，從左到右表示掃描線上測高點的數(shù)據(jù)。每個數(shù)字都是不超過10^6的非負(fù)整數(shù)。
s代表掃描線的條數(shù)。
p代表編號為奇數(shù)的掃描線上的測高點數(shù)，編號為偶數(shù)的掃描線上有p+1個測高點。
d代表無視海拔時，每個測高點與距其最近的測高點的距離（即三角形的邊長）。
h代表等高線的海拔間隔。在最后的等高線圖中，在所有海拔為h的整數(shù)倍的地方都會有一條等高線。注意一張地圖上同一海拔的等高線可能有多條。當(dāng)一整塊區(qū)域水平時，只在邊界處有等高線（見圖2中海拔為9的等高線）。
接下來共s行，每行描述一條掃描線。對于奇數(shù)行，每行含有p個整數(shù)，從左到右表示掃描線上測高點的數(shù)據(jù)。對于偶數(shù)行，每行含有p+1個整數(shù)，從左到右表示掃描線上測高點的數(shù)據(jù)。每個數(shù)字都是不超過10^6的非負(fù)整數(shù)。
輸出格式
輸出一個整數(shù)，表示繪制的等高線圖上所有等高線的長度之和，四舍五入到最近的整數(shù)。
樣例輸入
3 2 5 5 1 1 1 9 1 1 1
樣例輸出
15