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

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

소

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

요약
나무 좌표가 최대 10000개 주어질 때, 일부를 꼭짓점으로 하는 가장 큰 볼록 다각형을 찾아 그 넓이를 50으로 나눈 몫을 구한다.
난이도

보통10점 중 6점

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

문제

농부들은 비용을 아끼기 위해 땅에 자라는 나무를 울타리 기둥으로 사용해 가능한 한 넓은 목초지를 만들려고 합니다. 여러 나무의 위치가 주어집니다. 이 나무들 중 일부 또는 전부를 꼭짓점으로 사용해 만들 수 있는 가장 넓은 목초지(볼록 다각형)를 생각하세요. 모든 나무를 사용할 필요는 없습니다.

구해야 하는 것은 그 목초지에 몇 마리의 소를 둘 수 있는지입니다. 소 한 마리가 살아남으려면 최소 5050 제곱미터의 목초지가 필요합니다. 따라서 만들 수 있는 가장 넓은 목초지의 넓이를 5050으로 나눈 몫(소수점 이하 버림)이 답입니다.

입력

첫째 줄에 땅에 자라는 나무의 수를 나타내는 정수 nn (1≤n≤100001 \le n \le 10000)이 주어집니다. 다음 nn개의 줄에는 각 나무의 정수 좌표가 공백으로 구분된 두 정수 xx와 yy로 주어집니다 (−1000≤x,y≤1000-1000 \le x, y \le 1000). 좌표의 한 단위는 정확히 11미터에 대응합니다. 예를 들어 좌표 (10,11)(10, 11)과 (11,11)(11, 11) 사이의 거리는 11미터입니다.

출력

만들 수 있는 가장 넓은 목초지에서 살아남을 수 있는 소의 마릿수를 정수 하나로 출력하세요.

예제1

  1. 예제 1

    입력
    4
    0 0
    0 101
    75 0
    75 101
    
    예상 출력
    151