| Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
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łowego | 50000B |
| 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)? |
RSS