문제 설명
농부 존은 그가 키우는 소들에게 삼각형 모양의 목장을 짓고 싶어한다.
농장 2D 지도에는 총 N개의 울타리 기둥(3 ≤ N ≤ 100)이 각각 점 (X1, Y1) ... (XN, YN) 위치에 나타나 있다. 존은 삼각형의 한 변은 x축과 평행하게 하고 다른 한 변은 y축과 평행할 수 있게 3개의 점을 선택해서 삼각형 모양의 목장을 만들 수 있다. 농부 존이 만들 수 있는 목장의 최대 면적은 얼마인가? 적어도 하나의 삼각형 목장이 존재한다.
입력 설명
입력의 첫 번째 줄에는 정수 N이 주어진다. 그 다음 N개의 라인에는 울타리 기둥의 위치를 나타내는 Xi, Yi가 주어진다. (-104 ≤ Xi, Yi ≤ 104)
출력 설명
삼각형의 넓이는 정수가 아닐 수 있어서 출력은 삼각형 목장의 최대 면적의 2배에 해당하는 값을 출력한다.
20
-2642 1321
-1321 2642
-2642 0
0 -1321
3963 1321
3963 -3963
0 -2642
-1321 -1321
0 -3963
2642 -1321
2642 3963
-2642 2642
2642 -3963
0 2642
-2642 -3963
3963 0
3963 -1321
-1321 -2642
-3963 -2642
-2642 -1321
도움
(0, 0), (1, 0), (1, 2)로 만들어진 삼각형의 넓이는 1이다. 이 넓이에 2를 곱한 2가 정답이다. 만들 수 있는 삼각형이 하나 더 있다. 이 삼각형의 넓이는 0.5다.