아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

고질라를 가두어라!

시간 제한1초메모리 제한128 MB

요약
n개의 점 중 세 점을 골라 만들 수 있는 넓이가 0이 아닌 가장 작은 삼각형의 넓이의 두 배를 구합니다.
난이도

어려움10점 중 8점

유형
기하, 정렬, 투 포인터
정답자
아직 제출이 없습니다

문제

고질라를 잡았다! 텔레비전 케이블을 마구 갉아먹던 고질라를 드디어 붙잡는 데 성공했다. 이제 남은 문제는 이 녀석을 어디에 가둘 것인가이다.

누군가 삼각형 울타리로 고질라를 가두자는 아이디어를 냈다. 울타리의 세 꼭짓점에는 저마다 숲에 자라는 나무가 한 그루씩 서 있어야 한다. 다시 말해, 주어진 나무들 중 세 그루를 골라 그 위치를 꼭짓점으로 삼는 삼각형 부지를 만든다.

숲을 최대한 넓게 남겨 두려면, 고질라가 차지하는 삼각형 부지의 넓이를 될 수 있는 한 작게 만들어야 한다. 이 삼각형 부지가 얼마나 작아질 수 있는지 구하여라.

입력

첫째 줄에 나무의 개수 nn 이 주어진다 (3≤n≤20003 \le n \le 2000).

이어지는 nn 개의 줄에는 각 나무의 좌표를 나타내는 두 정수 xix_i, yiy_i 가 공백으로 구분되어 주어진다 (−109≤xi,yi≤109-10^9 \le x_i, y_i \le 10^9).

같은 위치에 두 그루 이상의 나무가 서 있는 경우는 없으며, 모든 나무가 한 직선 위에 놓여 있지도 않다.

출력

세 나무를 꼭짓점으로 만들 수 있는 삼각형 가운데 넓이가 가장 작은 것을 찾아, 그 넓이의 두 배에 해당하는 정수 하나를 출력한다.

세 점이 한 직선 위에 놓여 넓이가 00 이 되는 퇴화 삼각형은 고려하지 않는다. 그런 곳에는 고질라를 가둘 수 없기 때문이다.

모든 좌표가 정수이므로 넓이의 두 배는 항상 정수가 된다는 점에 유의한다.

예제5

  1. 예제 1

    입력
    5
    -7 4
    -7 2
    7 -2
    -5 5
    5 -4
    
    예상 출력
    4
    
  2. 예제 2

    입력
    3
    0 0
    1 0
    0 1
    
    예상 출력
    1
    
  3. 예제 3

    입력
    3
    0 0
    4 0
    0 4
    
    예상 출력
    16
    
  4. 예제 4

    입력
    4
    0 0
    1 0
    2 0
    5 7
    
    예상 출력
    7
    
  5. 예제 5

    입력
    6
    0 0
    1 0
    2 0
    3 0
    10 0
    0 1
    
    예상 출력
    1