Module: 삼항 검색


Problem

7 /9


부하 분산

Problem

<사업부> 농부 John의 소는 서로 다른 지점에 있습니다 (x1,y1)…(xn,yn ) 해당 필드(1≤N≤100,000, 모든 xi 및 yi는 1,000,000을 초과하지 않는 양의 홀수 정수입니다. FD는 자신의 필드를 무한대 펜스로 나누고자 합니다. 방정식 x=a로 설명되는 북쪽에서 남쪽까지의 길이(a는 짝수이므로 울타리가 소의 위치를 ​​통과하지 않도록 합니다.) 그는 또한 무한 길이의 울타리를 만들고 싶어합니다. 동쪽에서 서쪽으로, 방정식 y=b로 설명됩니다. 여기서 b는 짝수 정수입니다. 이 두 울타리는 (a,b)에서 교차하며 함께 필드를 4개의 영역으로 나눕니다.
<사업부> FD는 "균형"을 얻는 방식으로 a와 b를 선택하려고 합니다. 모든 지역의 젖소 수, 즉 너무 많은 소를 포함하는 지역이 없도록. M을 이 4개 지역의 최대 젖소 수라고 하면 FD는 M이 가능한 한 작아지길 원합니다. FD가 M에 대해 가능한 최소값을 결정하도록 도와주세요.
<사업부>  
<사업부> 입력 형식:
<사업부> 첫 번째 입력 라인에는 하나의 정수 N이 포함됩니다. 다음 n개의 각 라인에는 x 및 y 좌표로 표시된 소 한 마리의 위치가 포함됩니다.
<사업부> 출력 형식:
<사업부> 최적의 펜스 배치로 PD에 도달할 수 있는 M의 최소값을 인쇄합니다.

<몸>

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

엔터 출력
<사업부> 7 <사업부> 73 <사업부> 5 5 <사업부> 7 13 <사업부> 3 1 <사업부> 117 <사업부> 5 3 <사업부> 9 1 2