시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB511991710.625%

문제

N개의 점들로 이루어진 산맥이 있다. 편의상 각각의 점들의 x좌표는 모두 다르다고 가정하자. 이 점들을 x좌표가 증가하는 순서로 연결하면 산맥의 모양이 나온다.

때로는 산맥의 모양이 복잡하기 때문에 산맥을 그리는 것이 힘들 때가 있다. 이럴 경우에, 산맥의 양쪽 끝점과 그 사이의 K개의 점, 즉 총 K+2개의 점으로 산맥을 근사시켜 그리려고 한다. 이때, 원래의 산맥과 근사시킨 산맥에서 부분적으로 차이가 나는 부분의 넓이의 합을 최소로 하려 한다.

검은색이 원래 산맥이고 빨간색이 근사시킨 산맥일 때, 회색으로 칠해진 부분의 넓이의 합이 부분적으로 차이가 나는 부분의 넓이의 합이다.

입력

첫째 줄에 n(3 ≤ n ≤ 100), K(0 ≤ K ≤ n-2)가 주어진다. 다음 n개의 줄에는 산맥의 각 점의 x, y좌표가 주어진다. 각 좌표는 x좌표가 증가하는 순서대로 주어진다. 각 점의 좌표는 500을 넘지 않는 자연수이다.

출력

첫째 줄에 부분적으로 차이가 나는 부분의 넓이의 합의 최솟값을 출력한다. 절대/상대 오차는 10-6까지 허용한다.

예제 입력 1

4 1
1 1
2 2
3 2
4 1

예제 출력 1

0.5

출처

  • 빠진 조건을 찾은 사람: koosaga