시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB274574627.219%

문제

2차원 평면 상에 서로 다른 $N$개의 점이 주어진다. 제노는 이 점들 중 $K$개 이하의 점들을 골라 단순다각형을 만들려고 한다. 제노가 만들 수 있는 단순다각형의 최대 넓이를 구하시오.

입력

첫째 줄에는 $N,\ K$가 공백을 사이에 두고 주어진다. ($K \le N \le 400,\ 3 \le K \le \min (12,N)$)

둘째 줄부터 $N+1$번째 줄까지 각 점의 $x,\ y$ 좌표가 공백을 사이에 두고 주어진다.

좌표값은 절댓값이 $10^5$을 넘지 않는 정수이다.

출력

첫째 줄에 최대 넓이를 소수점 아래 둘째 자리에서 반올림하여 첫째 자리까지 출력한다.

주어진 입력으로 넓이가 0 초과인 단순다각형을 만들 수 있음이 보장된다.

예제 입력 1

8 3
10 -1
5 4
-4 2
-8 -2
1 -5
-5 4
-2 1
3 3

예제 출력 1

52.5

(-5, 4), (-8, -2), (10, -1)의 세 점을 선택하면, 넓이가 52.5인 삼각형을 만들 수 있다.

예제 입력 2

20 5
80000 20000
26435 29423
79100 20900
50000 50000
46245 47499
56145 -316
46512 -7169
58092 32650
50000 -10000
72169 49362
23220 -8321
23973 -9148
25313 25419
76567 9094
28024 -9877
54035 24956
41587 -6615
20000 20000
37842 42884
31457 18570

예제 출력 2

2259785373.0