삼각형 (Bronze)

면접 대비

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

요약
최대 100개의 점 중에서 한 변은 x축에, 다른 한 변은 y축에 평행한 삼각형을 골라 넓이의 두 배의 최댓값을 구한다.
난이도

쉬움10점 중 3점

유형
완전 탐색, 기하, 구현
정답자
아직 제출이 없습니다

문제

농부 John은 소를 위한 삼각형 목초지를 만들려고 한다.

농장의 2차원 지도 위에 서로 다른 점 (X1,Y1)…(XN,YN)(X_1, Y_1) \ldots (X_N, Y_N)에 NN개의 울타리 기둥이 있다 (3≤N≤1003\le N\le 100). John은 이 중 세 개를 골라 삼각형 목초지의 꼭짓점으로 삼을 수 있는데, 삼각형의 한 변은 xx축에 평행하고 다른 한 변은 yy축에 평행해야 한다.

John이 만들 수 있는 목초지의 최대 넓이는 얼마인가? 유효한 삼각형 목초지가 적어도 하나 존재함이 보장된다.

입력

입력의 첫째 줄에는 정수 NN이 주어진다. 다음 NN개의 줄에는 각각 두 정수 XiX_i와 YiY_i가 주어지며, 각 값은 −104-10^4 이상 10410^4 이하이다. 이는 울타리 기둥의 위치를 나타낸다.

출력

넓이가 반드시 정수인 것은 아니므로, 울타리 기둥으로 만들 수 있는 유효한 삼각형의 최대 넓이의 두 배를 출력한다.

힌트

(0,0)(0,0), (1,0)(1,0), (1,2)(1,2)에 있는 기둥은 넓이가 11인 삼각형을 이룬다. 따라서 답은 2⋅1=22\cdot 1=2이다. 다른 삼각형은 넓이가 0.50.5인 것 하나뿐이다.

예제1

  1. 예제 1

    입력
    4
    0 0
    0 1
    1 0
    1 2
    
    예상 출력
    2