세력권 넓히기

통제 중인 k개의 점이 이루는 볼록 껍질이 주어질 때, 나머지 점 하나를 추가해 얻을 수 있는 최대 볼록 껍질 넓이를 소수점 한 자리까지 구한다.

어려움8기하그리디정렬이분 탐색아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

어두운 숲에서 당신은 나무 몇 그루를 지배한다. 지배하는 나무를 모두 담는 가장 작은 볼록 도형이 당신의 세력권이고, 그 도형의 넓이가 곧 세력의 크기다. 지배하는 나무가 경계가 아니라 세력권 내부에 있어도 된다.

숲에 있는 나무 nn그루 가운데 kk그루를 지배하고 있다. 숲의 어느 나무든 한 그루를 더 지배해서 세력을 넓히려 한다. 세력을 가장 많이 키우는 나무 한 그루를 얻은 뒤, 새 도형의 넓이는 얼마인가?

입력

입력은 테스트 케이스 하나로 이루어진다. 프로그램은 서로 다른 입력으로 여러 번 실행될 수 있다.

첫째 줄에 정수 nnkk가 주어진다 (3k<n1000003 \le k < n \le 100\,000). nn은 숲에 있는 나무의 총 수이고, kk는 지배하는 나무의 수다.

다음 nn개 줄에는 나무 한 그루의 위치를 나타내는 정수 xxyy가 주어진다 (109x,y109-10^9 \le x, y \le 10^9). 목록에서 앞의 kk그루가 지배하는 나무다. 어떤 세 나무도 한 직선 위에 있지 않다. 지배하지 않는 나무가 세력권 안에 있을 수도 있다.

출력

나무 한 그루를 더 지배해서 얻을 수 있는 가장 큰 넓이를 소수점 아래 한 자리까지 정확히 출력한다. 좌표가 모두 정수이므로 이 넓이는 항상 0.50.5의 배수다.