Problem
As vacas do fazendeiro John estão em pontos diferentes (x1,y1)…(xn,yn ) seus campos (1≤N≤100,000, todos xi e yi são números inteiros ímpares positivos que não excedem 1.000.000. O DF deseja dividir seu campo com uma cerca de infinito comprimento de norte a sul, descrito pela equação x=a (a é um número inteiro par, então é garantido que a cerca não passe pela posição de nenhuma vaca). Ele também quer construir uma cerca de comprimento infinito de leste a oeste, que é descrito pela equação y=b, onde b é um número inteiro par. Essas duas cercas se cruzam em (a,b) e juntas dividem o campo em quatro regiões.
O DF quer escolher a e b de forma que eles obtenham um "balanceamento" número de vacas em todas as regiões, ou seja, para que não haja nenhuma região que contenha muitas vacas. Seja M o número máximo de vacas nessas quatro regiões, o DF quer que M seja o menor possível. Ajude FD a determinar este valor mínimo possível para M.
FORMATO DE ENTRADA:
A primeira linha de entrada contém um inteiro, N. Cada uma das próximas n linhas contém a localização de uma vaca, indicada por suas coordenadas x e y.
FORMATO DE SAÍDA:
Imprima o valor mínimo possível de M que pode atingir o PD com o arranjo ótimo das cercas.
|
Entrar |
Saída |
|
7
73
5 5
7 13
3 1
117
5 3
9 1
|
2 |