RiseOJ – 삼각형

설명

농부 존은 소들을 위해 삼각형 모양의 목초지를 만들고 싶다.

그의 농장 2차원 지도 위의 서로 다른 점 $(X_1, Y_1) \ldots (X_N, Y_N)$ 에 $$N$$ 개의 울타리 기둥( $3\le N\le 100$ )이 있다. 삼각형의 한 변이 $$x$$ 축과 평행하고 다른 한 변이 $$y$$ 축과 평행하기만 하면, 그중 세 개를 골라 삼각형 목초지의 꼭짓점으로 삼을 수 있다.

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

문제 제공: Travis Hance

제약

문제 제공: Travis Hance

입력 형식

첫째 줄에 정수 $$N$$ 이 주어진다. 다음 $$N$$ 개의 줄에는 각각 울타리 기둥의 위치를 나타내는 두 정수 $$X_i$$ 와 $$Y_i$$ 가 주어지며, 각각 $-10^4 \ldots 10^4$ 범위(양 끝 포함)에 있다.

출력 형식

넓이 자체는 정수가 아닐 수 있으므로, 울타리 기둥으로 만들 수 있는 유효한 삼각형의 최대 넓이의 두 배를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 triangles.in · 출력을 쓸 파일 triangles.out

예제 1

입력

출력

설명

Posts at $$(0,0)$$ , $$(1,0)$$ , and $$(1,2)$$ form a triangle of area $$1$$ . Thus, the
answer is $2\cdot 1=2$ . There is only one other triangle, with area $$0.5$$ .

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > February > Bronze

올림피아드 > USACO > 2019-2020 > February > Bronze

태그

JudgeUSACO

삼각형

평가 및 의견

풀이 제출