아름다운 다리

우리를 모두 이어 주는 것은 무엇일까? 흔히 그것은 다리다. 고대부터 사람들은 도로, 철도, 보행자를 위한 다리를 지었고, 물을 나르는 수도교도 만들었다. 불편한 지형을 그대로 받아들이지 않으려는 인류의 방식이다.

Arch Bridges Construction(ABC)은 이름 그대로 아치교 건설을 전문으로 한다. 이 고전적인 양식의 다리는 다리 아래 지면에서 뻗어 나온 교각으로 지탱된다. 교각 사이의 아치는 다리의 무게를 인접한 교각에 분산한다.

ABC가 짓는 다리는 교각 간격이 일정하지 않은 경우가 많다. 미적인 이유로 ABC의 다리는 항상 반원형 아치를 사용한다(그림 B.1). 다만 다리의 아치는 지면에 닿을 수는 있어도 지면 아래로 내려갈 수는 없다. 그래서 어떤 교각 배치는 불가능하다.

(a) 거리 d만큼 떨어진 연속한 교각은 반지름 r = d/2인 반원형 아치로 연결된다.	(b) 잘못된 교각 배치(아치가 지면 아래로 내려갈 수 없다).	(c) 예제 입력 1에 대응하는 다리.

그림 B.1: 다리 예시.

지면 프로파일과 원하는 다리 높이 h가 주어지면, 아치교를 짓는 방법은 보통 여러 가지다. 지면 프로파일은 n개의 주요 점 (x1, y1),(x2, y2), . . . ,(xn, yn)으로 표현되는 구간별 선형 함수로 모델링한다. 점의 x좌표는 다리를 따라가는 위치이고, y좌표는 이 위치에서 해수면 위 지면의 고도다. 첫 교각과 마지막 교각은 첫 주요 점과 마지막 주요 점에 세워야 하고, 중간 교각은 이 주요 점에만 세울 수 있다. 다리의 비용은 교각 비용(높이에 비례)과 아치 비용(사용한 재료의 양에 비례)의 합이다. 따라서 높이가 h1, . . . , hk인 k개의 교각이 수평 거리 d1, . . . , dk−1만큼 떨어져 있는 다리의 총비용은 주어진 상수 α와 β에 대해

[\alpha \cdot \sum_{i=1}^{k}{h_i} + \beta \cdot \sum_{i=1}^{k-1}{d_i^2}]

이다. ABC는 각 다리를 가능한 한 가장 낮은 비용으로 짓고자 한다.

입력의 첫 줄에는 네 정수 n, h, α, β가 주어진다. n (2 ≤ n ≤ 104)은 지면 프로파일을 나타내는 점의 수, h (1 ≤ h ≤ 105)는 해수면 위 다리의 원하는 높이, α, β (1 ≤ α, β ≤ 104)는 앞에서 설명한 비용 계수다. 이어서 n개의 줄이 주어지고, i번째 줄에는 두 정수 xi, yi (0 ≤ x1 < x2 < . . . < xn ≤ 105이고 0 ≤ yi < h)가 주어지며 지면 프로파일을 나타낸다.

수평 위치 x1에서 xn까지 해수면 위 높이 h로 다리를 지을 때의 최소 비용을 출력한다. 그러한 다리를 지을 수 없으면 impossible을 출력한다.