Problem
Die Kühe von Bauer John stehen an verschiedenen Stellen (x1,y1)…(xn,yn) seine Felder (1≤N≤100,000, alle xi und yi sind positive ungerade ganze Zahlen, die nicht größer als 1,000,000 sind. Die FD möchte ihr Feld mit einer Hecke von unendlicher Länge von Norden nach Süden teilen, die durch die Gleichung x=a beschrieben wird (a ist eine gerade ganze Zahl, so dass sichergestellt wird, dass die Hecke nicht durch die Position einer Kuh verläuft). Er möchte auch eine Hecke von unendlicher Länge von Ost nach West bauen, die durch die Gleichung y=b beschrieben wird, wobei b eine gerade ganze Zahl ist. Diese beiden Hecken schneiden sich am Punkt (a, b) und teilen das Feld zusammen in vier Regionen.
Die FD möchte a und b so wählen, dass sie eine "ausgewogene" Anzahl von Kühen in allen Regionen erhalten, dh dass es keine Region gibt, die zu viele Kühe enthält. Sei M die maximale Anzahl von Kühen in diesen vier Regionen, die FD möchte, dass M so klein wie möglich ist. Helfen Sie der PD, diesen minimal möglichen Wert für M. zu bestimmen.
EINGABEFORMAT:
Die erste Eingabezeile enthält eine ganze Zahl, N. Jede der folgenden n Zeilen enthält die Position einer Kuh, die durch ihre x- und y-Koordinaten angegeben ist.
AUSGABEFORMAT:
Geben Sie den kleinstmöglichen M-Wert aus, den die FD durch die optimale Anordnung der Hecken erreichen kann.
|
Eingabe |
Ausgabe |
|
7
7 3
5 5
7 13
3 1
11 7
5 3
9 1
|
2 |