폴리라인 단순화

지도 애플리케이션은 나라나 도시의 경계를 선분을 이어 붙인 폴리라인으로 나타낸다. 사용자가 지도를 확대하면 세밀한 부분까지 보여야 하므로 이런 폴리라인은 선분이 아주 많다. 반대로 축소하면 세밀한 부분은 중요하지 않고, 선분이 그렇게 많은 폴리라인을 처리하고 그리는 것은 낭비다. 이 문제에서는 원래 폴리라인을 선분이 더 적은 폴리라인으로 근사하는 폴리라인 단순화 알고리즘을 다룬다.

선분이 $n$개인 폴리라인은 점 $n + 1$개 $p_0 = (x_0, y_0), \dots, p_n = (x_n, y_n)$으로 나타내고, $i$번째 선분은 $p_{i-1}$과 $p_i$를 잇는다. 내부 점 $p_i$ ($1 \le i \le n - 1$)를 지우면 선분 $p_{i-1}p_i$와 $p_i p_{i+1}$이 선분 $p_{i-1}p_{i+1}$ 하나로 바뀌면서 폴리라인이 단순해진다. 지울 점은 이렇게 고른다. 내부 점 $p_i$마다 $p_{i-1}$, $p_i$, $p_{i+1}$이 이루는 삼각형의 넓이를 구하고(세 점이 한 직선 위에 있으면 넓이는 $0$이다), 그 넓이가 가장 작은 점을 지운다. 넓이가 가장 작은 점이 여럿이면 원래 폴리라인에서 번호가 가장 작은 점을 지운다. 남은 폴리라인에 같은 규칙을 다시 적용해서, 선분이 원하는 개수인 $m$개가 될 때까지 되풀이한다.

아래 그림은 한 단계를 보여 준다.

맨 위가 원래 폴리라인이다. 가운데에서는 $p_2$, $p_3$, $p_4$가 이루는 삼각형의 넓이를 재고, 이 넓이가 모든 삼각형 중에서 가장 작으면 $p_3$을 지운다. 맨 아래가 $p_3$을 지운 뒤의 폴리라인이다.

첫째 줄에 정수 $n$ ($2 \le n \le 200\,000$)과 $m$ ($1 \le m < n$)이 주어진다. 이어지는 $n + 1$개의 줄에 $p_0$부터 $p_n$까지가 차례대로 주어진다. 각 줄에는 점의 $x$ 좌표와 $y$ 좌표가 주어지고, 두 값 모두 $-5000$ 이상 $5000$ 이하의 정수다. 주어지는 점은 사전순으로 엄격하게 증가한다. 즉 모든 $0 \le i < n$에 대해 $x_i < x_{i+1}$이거나, $x_i = x_{i+1}$이면서 $y_i < y_{i+1}$이다.

$n - m$개의 줄을 출력한다. $k$번째 줄에는 위 알고리즘의 $k$번째 단계에서 지운 점의 번호를 출력한다. 번호는 원래 폴리라인에서의 번호를 쓴다.