5289 - Contour Mapping ?

描述

　　等高线图可以描绘一个区域的地势。等高线图上的等高线代表等高海拔。比如，一张等高线图上可能有一条线代表海拔100米的区域，另一条代表海拔200米的区域等等。
　　等高线图绘制协会（Association for Contour Mapping，简称ACM）需要程序读取从卫星获取的海拔信息并绘制等高线图。ACM尤其关注每张地图上所有等高线的长度之和。海拔信息的形式为一个整数序列，依次代表在一条从西往东的扫描线上取的等距离的点的海拔。扫描线间距的取值使得测量区域内所有不在边缘的每个测高点都有6个其他的测高点离它最近，而且相互等距（这里忽视海拔高度），如图1和图2所示。

　ACM的做法是，用线段连接每个点与距其最近的所有点，构造出许多三角形，并用这些三角形来估计实际地形。每个三角形会被视为一个平面，由其三个顶点的坐标和海拔确定。如果把三角形投影到海平面上，这些三角形会是等边三角形。
　　在上图中，黑色的数字代表海拔信息，红色虚线和数字代表等高线。图1中有一条海拔为5的等高线。图2中在海拔为6和9之处分别有一条等高线。等高线可以穿过三角形的内部或者紧贴三角形的一边。
　　由于测高点的特殊选取方式，编号为偶数的扫描线较之于编号为奇数的扫描线上会多取一个测高点。图中最上面的一条线是第一条扫描线。

　输入第一行有4个整数s、p、d和h。
　　s代表扫描线的条数。
　　p代表编号为奇数的扫描线上的测高点数，编号为偶数的扫描线上有p+1个测高点。
　　d代表无视海拔时，每个测高点与距其最近的测高点的距离（即三角形的边长）。
　　h代表等高线的海拔间隔。在最后的等高线图中，在所有海拔为h的整数倍的地方都会有一条等高线。注意一张地图上同一海拔的等高线可能有多条。当一整块区域水平时，只在边界处有等高线（见图2中海拔为9的等高线）。
　　接下来共s行，每行描述一条扫描线。对于奇数行，每行含有p个整数，从左到右表示扫描线上测高点的数据。对于偶数行，每行含有p+1个整数，从左到右表示扫描线上测高点的数据。每个数字都是不超过10^6的非负整数。

　输出一个整数，表示绘制的等高线图上所有等高线的长度之和，四舍五入到最近的整数。

数据规模和约定

　　对于10%的数据，s = 2，p = 1。
　　对于30%的数据，保证图中所有等高线的海拔相同。
　　对于60%的数据，保证任意测高点的海拔都不是h的整数倍。
　　对于100%的数据，2 ≤ s ≤ 100，1 ≤ p ≤ 100，1 ≤ d ≤ 10，1 ≤ h ≤ 1000。

蓝桥杯