아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

다각형의 넓이

시간 제한1초메모리 제한1024 MB

요약
주어진 N개의 점 중 최대 K개를 골라 넓이가 최대인 단순 다각형을 만들고, 그 넓이를 소수 첫째 자리까지 출력한다.
난이도

어려움10점 중 8점

유형
기하, 동적 계획법, 정렬, 조합론
정답자
아직 제출이 없습니다

문제

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

입력

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

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

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

출력

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

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

예제2

  1. 예제 1

    입력
    8 3
    10 -1
    5 4
    -4 2
    -8 -2
    1 -5
    -5 4
    -2 1
    3 3
    
    예상 출력
    52.5
    
  2. 예제 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
    
    예상 출력
    2259785373.0