만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

사각형 돗자리

시간 제한5초메모리 제한128 MB

요약
N개의 점과 넓이 한계 L이 주어질 때, 단순 사각형을 이루는 네 점을 골라 넓이가 L 이하이면서 최대가 되도록 한다.
난이도

어려움10점 중 8점

유형
기하, 완전 탐색, 정렬, 이분 탐색
정답자
아직 제출이 없습니다

문제

미르코는 데이지 꽃을 좋아한다. 소풍을 갈 때마다 사각형 모양 돗자리를 새로 만든다. 돗자리를 풀밭에 펼칠 때는 사각형의 네 꼭짓점이 풀밭에 자란 데이지 위치와 정확히 일치하기를 바란다. 일행이 많아 모두 앉을 수 있도록 넓이가 최대인 돗자리를 만들려 하지만, 가진 천이 LL 제곱미터뿐이라 돗자리의 넓이는 LL 이하여야 한다.

풀밭에 자란 데이지 NN송이의 좌표가 주어진다. 서로 다른 데이지 네 송이를 꼭짓점으로 골라 만들 수 있는 돗자리 중에서, 넓이가 LL 이하인 것의 최대 넓이를 구하라.

돗자리가 볼록할 필요는 없지만 넓이는 0보다 커야 한다. 미르코는 솜씨 좋은 재단사라서 천을 마음대로 자르고 붙여 어떤 사각형 모양이든 만들 수 있다. 네 꼭짓점 중 셋이 한 직선 위에 있어도 된다. 다만 사각형의 변끼리 교차해서는 안 되고, 이웃한 두 변은 공유하는 꼭짓점에서만 만나야 한다.

입력

첫째 줄에 데이지의 수 NN과 미르코가 가진 천의 넓이 LL이 주어진다. (4≤N≤3004 \le N \le 300, 1≤L≤1091 \le L \le 10^9)

다음 NN개의 줄에 데이지의 좌표 xx와 yy가 한 줄에 하나씩 주어진다. (−10000≤x,y≤10000-10000 \le x, y \le 10000) 같은 좌표에서 자라는 데이지는 없다.

출력

조건을 만족하는 돗자리의 최대 넓이를 소수점 아래 둘째 자리까지 출력한다. 넓이는 항상 0.5의 배수라 반올림 오차는 생기지 않는다. 조건을 만족하는 돗자리가 하나도 없으면 0.00을 출력한다.

예제3

  1. 예제 1

    입력
    4 7
    -1 -1
    -1 1
    1 1
    1 -1
    
    예상 출력
    4.00
    
  2. 예제 2

    입력
    7 21
    -4 -2
    -1 2
    -5 -1
    7 5
    2 3
    -10 1
    1 -2
    
    예상 출력
    21.00
    
  3. 예제 3

    입력
    4 9837
    -100 -100
    -100 100
    100 100
    100 -100
    
    예상 출력
    0.00