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.|

FR_09_14 - Minimalnie maksymalna

Minimalnie maksymalna

W układzie kartezjańskim, dla zadanych n punktów kratowych, znajdź takie rzeczywiste a, b, dla których proste x=a i y=b podzielą układ na cztery części tak, aby maksymalna liczba punktów kratowych jednej z czterech części była jak najmniejsza.

Wejście
W pierwszym wierszu wejścia znajduje się liczba punktów kratowych n (4 ≤ n ≤ 105). Dalej w n wierszach podane są współrzędne punktów kratowych, w każdym wierszu dwie liczby całkowite x, y (1 ≤ x, y ≤ 106).

Wyjście
Na wyjściu należy wypisać najmniejszą możliwą wartość, którą można osiągnąć dobierając odpowiednie wartości a i b.


Przykład

Wejście
7
3 1
5 3
9 1
6 3
5 4
8 10
11 6

Wyjście
2


Dodane przez:Mariusz Śliwiński
Data dodania:2018-05-21
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: ASM32-GCC COBOL D-CLANG D-DMD ELIXIR FANTOM GOSU GRV JS-MONKEY NIM OBJC OBJC-CLANG PICO RUST SCM qobi CHICKEN VB.NET

ukryj komentarze
2018-05-26 15:31:32 Mariusz ¦liwiñski
Proste x=a i y=b należy tak poprowadzić, aby nie należał do nich żaden punkt kratowy podany na wejściu.
2018-05-26 15:20:19
Jeżeli jakiś punkt leży na prostej x=a (lub y=b) to do ilu części on należy. W szczególności do ilu części należy punkt o współrzędnych (a,b)?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.