Triangle on the Axis

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

요약

정수 좌표 점 1000개 이하가 주어질 때, 한 변이 x축 위에 놓이는 삼각형의 최대 넓이를 구한다.

난이도: 보통10점 중 4점
유형: 기하, 완전 탐색
정답자: 아직 제출이 없습니다

문제

You are given a set of points on a plane with integer coordinates. Find a triangle with the largest area whose vertices belong to this set of points, with one of its sides lying on the $Ox$ axis.

입력

The first line contains an integer $n$ : the number of points ( $1 \le n \le 1000$ ). Each of the following $n$ lines contains two integers $x$ and $y$ : the coordinates of the points. All coordinates do not exceed $1000$ by absolute value.

출력

Output a single real number: the maximum area of the triangle that satisfies the problem's conditions. If there is no such triangle or it is degenerate, output $0$ .

Your answer will be considered correct if it differs from the exact value by no more than $10^{-9}$ .

힌트

Pictures for the examples:

예제2

예제 1
입력
```
3
0 0
1 0
2 -3
```
예상 출력
```
1.5
```
예제 2
입력
```
3
1 0
2 1
3 3
```
예상 출력
```
0
```