사각형 돗자리
시간 제한5초메모리 제한128 MB
N개의 점과 넓이 한계 L이 주어질 때, 단순 사각형을 이루는 네 점을 골라 넓이가 L 이하이면서 최대가 되도록 한다.
문제
미르코는 데이지 꽃을 좋아한다. 소풍을 갈 때마다 사각형 모양 돗자리를 새로 만든다. 돗자리를 풀밭에 펼칠 때는 사각형의 네 꼭짓점이 풀밭에 자란 데이지 위치와 정확히 일치하기를 바란다. 일행이 많아 모두 앉을 수 있도록 넓이가 최대인 돗자리를 만들려 하지만, 가진 천이 제곱미터뿐이라 돗자리의 넓이는 이하여야 한다.
풀밭에 자란 데이지 송이의 좌표가 주어진다. 서로 다른 데이지 네 송이를 꼭짓점으로 골라 만들 수 있는 돗자리 중에서, 넓이가 이하인 것의 최대 넓이를 구하라.
돗자리가 볼록할 필요는 없지만 넓이는 0보다 커야 한다. 미르코는 솜씨 좋은 재단사라서 천을 마음대로 자르고 붙여 어떤 사각형 모양이든 만들 수 있다. 네 꼭짓점 중 셋이 한 직선 위에 있어도 된다. 다만 사각형의 변끼리 교차해서는 안 되고, 이웃한 두 변은 공유하는 꼭짓점에서만 만나야 한다.
입력
첫째 줄에 데이지의 수 과 미르코가 가진 천의 넓이 이 주어진다. (, )
다음 개의 줄에 데이지의 좌표 와 가 한 줄에 하나씩 주어진다. () 같은 좌표에서 자라는 데이지는 없다.
출력
조건을 만족하는 돗자리의 최대 넓이를 소수점 아래 둘째 자리까지 출력한다. 넓이는 항상 0.5의 배수라 반올림 오차는 생기지 않는다. 조건을 만족하는 돗자리가 하나도 없으면 0.00을 출력한다.