축 위의 삼각형

면접 대비

시간 제한2초메모리 제한2048 MB

요약

정수 좌표의 점들이 주어질 때, 한 변이 Ox 축 위에 놓이는 삼각형 중 넓이가 가장 큰 값을 구합니다. 그런 삼각형이 없으면 0을 출력합니다.

문제

평면 위에 정수 좌표를 가진 점들이 주어진다. 이 점들을 꼭짓점으로 하고, 한 변이 $Ox$ 축 위에 놓이는 삼각형 중에서 넓이가 가장 큰 삼각형을 찾는다.

첫 줄에 점의 개수 $n$ 이 주어진다 ( $1 \le n \le 1000$ ). 이어서 $n$ 개의 줄에 각각 정수 $x$ 와 $y$ 가 주어진다. 모든 좌표의 절댓값은 $1000$ 을 넘지 않는다.

조건을 만족하는 삼각형의 최대 넓이를 실수 하나로 출력한다. 그런 삼각형이 없거나 퇴화된 삼각형만 있으면 $0$ 을 출력한다. 답은 정확한 값과의 차이가 $10^{-9}$ 이하이면 정답으로 인정한다.

그림은 다음과 같다.