세력권 넓히기
시간 제한2초메모리 제한512 MB
통제 중인 k개의 점이 이루는 볼록 껍질이 주어질 때, 나머지 점 하나를 추가해 얻을 수 있는 최대 볼록 껍질 넓이를 소수점 한 자리까지 구한다.
문제
어두운 숲에서 당신은 나무 몇 그루를 지배한다. 지배하는 나무를 모두 담는 가장 작은 볼록 도형이 당신의 세력권이고, 그 도형의 넓이가 곧 세력의 크기다. 지배하는 나무가 경계가 아니라 세력권 내부에 있어도 된다.
숲에 있는 나무 그루 가운데 그루를 지배하고 있다. 숲의 어느 나무든 한 그루를 더 지배해서 세력을 넓히려 한다. 세력을 가장 많이 키우는 나무 한 그루를 얻은 뒤, 새 도형의 넓이는 얼마인가?
입력
입력은 테스트 케이스 하나로 이루어진다. 프로그램은 서로 다른 입력으로 여러 번 실행될 수 있다.
첫째 줄에 정수 과 가 주어진다 (). 은 숲에 있는 나무의 총 수이고, 는 지배하는 나무의 수다.
다음 개 줄에는 나무 한 그루의 위치를 나타내는 정수 와 가 주어진다 (). 목록에서 앞의 그루가 지배하는 나무다. 어떤 세 나무도 한 직선 위에 있지 않다. 지배하지 않는 나무가 세력권 안에 있을 수도 있다.
출력
나무 한 그루를 더 지배해서 얻을 수 있는 가장 큰 넓이를 소수점 아래 한 자리까지 정확히 출력한다. 좌표가 모두 정수이므로 이 넓이는 항상 의 배수다.