만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

최대 삼각형과 최소 삼각형

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

요약
평면 위 n개 점 중에서 세 점을 골라 만드는 삼각형의 넓이 중 가장 큰 값과 가장 작은 값을 구합니다.
난이도

어려움10점 중 9점

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

문제

평면 위에 점 nn개가 있다. 이 중에서 세 점을 고르면 삼각형이 하나 만들어진다. 만들 수 있는 삼각형 가운데 넓이가 가장 큰 것과 가장 작은 것의 넓이를 구하라. 고른 세 점이 한 직선 위에 있으면 그 삼각형의 넓이는 00으로 본다.

입력

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 점의 개수 nn(3≤n≤20003 \le n \le 2000)이 주어진다. 이어지는 nn개 줄에는 점의 좌표를 나타내는 두 정수 xx, yy(−10000≤x,y≤10000-10000 \le x, y \le 10000)가 공백을 사이에 두고 주어진다. 한 테스트 케이스 안에서 같은 점이 두 번 나오지는 않는다. 입력의 마지막 줄에는 00 하나만 주어지며, 이 줄은 테스트 케이스가 아니다.

출력

각 테스트 케이스마다 한 줄에 두 수를 출력한다. 넓이가 가장 작은 삼각형의 넓이를 먼저, 가장 큰 삼각형의 넓이를 그다음에 공백으로 구분해 출력한다. 두 값 모두 소수점 아래 한 자리까지 출력한다. 좌표가 모두 정수라서 넓이는 항상 0.50.5의 배수이고, 소수점 아래 한 자리로 오차 없이 나타낼 수 있다.

예제2

  1. 예제 1

    입력
    4
    -5 -5
    -4 3
    4 1
    3 -2
    7
    1 0
    2 0
    0 2
    2 3
    0 1
    3 0
    0 3
    0
    
    예상 출력
    10.5 33.0
    0.0 4.0
    
  2. 예제 2

    입력
    3
    0 0
    2 4
    5 10
    0
    
    예상 출력
    0.0 0.0