삼각형 목초지(Triangles)

농장에 N개의 울타리 기둥(3\le N\le 100)이 중복되지 않는 지점들 (X_1, Y_1) \ldots (X_N, Y_N)에 있다.

농부 존은 소를 위해 울타리 기둥 세 개를 골라 울타리를 둘러싸 삼각형 목초지를 만들고 싶어한다.

건축법 상 삼각형의 변 중 하나는 x-축과 평행하고, 다른 변 중 하나는 y-축과 평행해야 한다.

농부 존이 형성할 수 있는 목초지의 최대 면적은 얼마입니까? 적어도 하나의 유효한 삼각형 목초지가 존재하는 것이 보장된다.

입력

첫 줄에 정수 N이 주어진다.

이어 N줄에 걸쳐 i번째 울타리 기둥의 좌표인 두 정수 X_i와 Y_i가 주어진다. ( -10^4 \le X_i, Y_i \le 10^4)

출력

삼각형 목초지의 최대 넓이는 반드시 정수라는 보장은 없기에 최대 넓이의 두 배를 출력한다.

예제1

울타리 (0,0), (1,0), (1,2)를 선택하면 넓이가 1이 된다. 그러므로 2\cdot 1=2를 출력한다. 다른 가능한 삼각형의 넓이는 0.5이기에 답은 2이다.

출처

USACO 2020 February Bronze

삼각형 목초지(Triangles) 2초 512MB