Problem
Le mucche del contadino John sono in punti diversi (x1,y1)…(xn,yn ) i suoi campi (1≤N≤100.000, tutti gli xi e yi sono numeri interi dispari positivi non superiori a 1.000.000. Il FD vuole dividere il suo campo con un recinto di infinite lunghezza dal nord al sud, descritta dall'equazione x=a (a è un numero intero pari, quindi è garantito che il recinto non passi attraverso la posizione di nessuna mucca). Vuole anche costruire un recinto di lunghezza infinita da est a ovest, che è descritto dall'equazione y=b, dove b è un numero intero pari Questi due recinti si intersecano in (a,b) e insieme dividono il campo in quattro regioni.
Il FD vuole scegliere a e b in modo tale da ottenere un "bilanciato" numero di vacche in tutte le regioni, vale a dire in modo che non ci sia regione che contenga troppe mucche. Sia M il numero massimo di vacche in queste quattro regioni, il FD vuole che M sia il più piccolo possibile. Aiuta FD a determinare questo valore minimo possibile per M.
FORMATO DI IMMISSIONE:
La prima riga di input contiene un numero intero, N. Ognuna delle successive n righe contiene la posizione di una mucca, indicata dalle sue coordinate x e y.
FORMATO DI USCITA:
Stampa il valore minimo possibile di M che può raggiungere il PD con la disposizione ottimale delle barriere.
|
Entra |
Uscita |
|
7
73
5 5
7 13
3 1
117
5 3
9 1
|
2 |