Problem
Las vacas del granjero John están en diferentes puntos (x1,y1)…(xn,yn ) sus campos (1≤N≤100,000, todos los xi y yi son enteros impares positivos que no exceden 1,000,000. El FD quiere dividir su campo con una valla de infinito longitud de norte a sur, descrita por la ecuación x=a (a es un número entero par, por lo que se asegura que la cerca no pase por la posición de ninguna vaca). También quiere construir una cerca de longitud infinita de este a oeste, que se describe mediante la ecuación y=b, donde b es un número entero par Estas dos cercas se cruzan en (a,b) y juntas dividen el campo en cuatro regiones.
El FD quiere elegir a y b de tal manera que obtengan un "equilibrado" número de vacas en todas las regiones, es decir, para que no haya región que contenga demasiadas vacas. Sea M el número máximo de vacas en estas cuatro regiones, el FD quiere que M sea lo más pequeño posible. Ayude a FD a determinar este valor mínimo posible para M.
FORMATO DE ENTRADA:
La primera línea de entrada contiene un número entero, N. Cada una de las siguientes n líneas contiene la ubicación de una vaca, indicada por sus coordenadas x e y.
FORMATO DE SALIDA:
Imprime el valor mínimo posible de M que puede alcanzar el PD con la disposición óptima de vallas.
|
Entrar |
Salida |
|
7
73
5 5
7 13
3 1
117
5 3
9 1
|
2 |