사각형 돗자리

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

어려움8기하완전 탐색정렬이분 탐색아직 제출이 없습니다시간 제한5초메모리 제한128 MB

문제

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

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

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

입력

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

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

출력

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