28091번 - 사각형 분할 스페셜 저지

문제

2차원 평면에 $N$개의 점을 포함하는 집합 $S = \{P_1,P_2,\cdots,P_N\}$와, 4개의 점을 포함하는 집합 $S' = \{(M,0),(0,M),(-M,0),(0,-M)\}$이 있다. 심심한 뉴비들은 $S \cup S'$에서 볼록 사각형을 이룰 수 있는 임의의 4개의 점을 고른 후, 그 위에 임의의 직선을 그어 사각형을 $(A 내부 점의 개수) = (B 내부 점의 개수)$를 만족하는 두 다각형 $A, B$로 분할하고자 한다. 이때 $(A의 넓이) \times (B의 넓이)$의 상한을 구하시오.

직선 위에 있는 점은 도형 내부에 있는 점의 개수에 포함되지 않으며 어떠한 세 점도 한 직선상에 존재하지 않고, 같은 점은 최대 1번만 주어진다.

입력

첫째 줄에 점의 개수 $N,ドル 꼭짓점의 좌표 $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 10^4; 1 \le M \le 10^9)$ 둘째 줄부터 $N$개의 줄에 걸쳐 xi yi의 형식으로 $P_i = (x_i,y_i)$가 주어진다. $(|x| \le M; |y| \le M)$

입력으로 주어지는 모든 수는 정수이다.

출력

$\text{(A의 넓이)} \times \text{(B의 넓이)}$의 상한을 출력한다. 절대/상대오차는 10ドル^{-6}$까지 허용한다.

제한

노트

상한은 수학적으로 다음과 같이 정의된다.