Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MWP8_1E - Sad

Michał posiada sad, w którym rośnie n jabłoni. Nasz bohater jest również ojcem czwórki dzieci, którym kiedyś ma zamiar przekazać swój majątek. Michał nie chce, aby jego potomstwo sprzeczało się o podział majątku, dlatego postanowił samemu podzielić sad na cztery części. Sadownik wypisał współrzędne x,y każdej z n jabłoni. Teraz ma zamiar poprowadzić dwie proste, jedną równoległą do osi odciętych, drugą równoległą do osi rzędnych, które to podzielą jego sad na cztery części. Proste nie mogą przechodzić przez punkty, w których rosną jabłonie. Nasz bohater chce, aby podział był możliwie jak najbardziej sprawiedliwy. Konkretnie rzecz ujmując zależy mu na tym, aby różnica pomiędzy częścią zawierającą najwiekszą liczbę jabłoni, a częścią zawierającą najmniejszą liczbę jabłoni była jak najmniejsza.

Twoim zadaniem jest wyznaczenie szukanej różnicy.

Wejście

W pierwszej linii znajduje się jedna liczba całkowita n ∈ [1;1000] określająca liczbę jabłoni rosnących w sadzie. W kolejnych n liniach znajdują się po dwie liczby całkowite x ∈ [0;109] i y ∈ [0;109] określające współrzędne jabłoni.

Wyjście

Na wyjściu należy wypisać szukaną różnicę.

Przykład

Wejście:

5
1 1
3 1
3 3
1 4
1 5

Wyjście:

1

Wyjaśnienie do przykładu:

Nasz bohater może poprowadzić prostą równoległą do osi odciętych przez punkt (0,2), zaś prostą równoległą do osi rzędnych przez punkt (2,0). W ten sposób uzyska cztery części o liczbie jabłoni: 1, 1, 1, 2, a zatem różnica pomiędzy najliczniejszą, a najmniej liczną częścią wynosi 1.


Dodane przez:Maciej Boniecki
Data dodania:2016-03-04
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
Pochodzenie:VIII Mistrzostwa WWSI w Programowaniu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.