Load Balancing Silver.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python, VB

¿Cada una de las N vacas del Granjero Juan están paradas en posiciones distintas (x_1, y_1) ... (x_n,y_n) en su granja bidimensional (1\leq N \leq 1000 y los x_i's y los y_i's son enteros positivos impares de tamaño a lo más 1,000,000). GJ quiere partir su campo construyendo una cerca larga (efectivamente de largo infinito) norte-sur con la ecuación x=a (a será un entero par, asegurando por lo tanto que no construye la cerca a través de la posición de ninguna vaca). El también quiere construir una cerca larga (efectivamente de largo infinito) este-oeste con la ecuación y=b, donde b es un entero par. Esas dos cercas se cruzan en el punto (a,b) y juntas parten su campo en cuatro regiones.

GJ quiere elegir a y b de tal manera que las vacas que aparecen en las cuatro regiones resultantes están razonablemente "balanceadas", sin ninguna región conteniendo demasiadas vacas. Si M es el número máximo de vacas que aparecen en una de las cuatro regiones, GJ quiere hacer M tan pequeño como sea posible. Por favor, ayúdelo a determinar este menor valor posible para M.

Entrada

La primera línea de la entrada contiene un solo entero, N. Cada una de las siguientes N líneas contiene la posición de una sola vaca, especificando sus coordenadas x y y.

Salida

Usted debe dar como salida el menor valor posible de M que GJ puede obtener posicionado sus cercas óptimamente.

Ejemplo de Entrada

7
7 3
5 5
7 13
3 1
11 7
5 3
9 1

Ejemplo de Salida

2

Comments

There are no comments at the moment.