← All solutions

The main difficulty in this problem is to get the contour lines that go along the border of the triangles. Ignoring this part for the time being, we compute the total length of contour lines within each triangle separately and add them up.

To compute the length of contour lines within a triangle where the three vertices have elevations h1 ≤ h2 ≤ h3, a somewhat inefficient way to do it is as follows: for each height h1 < z < h3 divisible by the parameter h, there is a contour line of height z within the triangle. The length of this contour line can be computed using basic trigonometry. However, doing this for all z ends up being too slow, as there can be a million contour lines in each of roughly 10000 triangles. To overcome this, note that the length of a contour line is linear in z in the range [h1, h2] and in the range [h2, h3], so the total length can be computed by twice using the closed formula for evaluating an arithmetic sum.

To handle the contour lines along the borders of the triangles, one can iterate through all borders and see if there is a contour line along them. This happens if the following two things happen:

• The two heights at the endpoints are equal and a multiple of h.
• At least one of the two other points of the two triangles that share the border have a height different from the height of the border (if the border is along the boundary of the triangulation this automatically happens).