Considerăm N segmente în planul XOY. Segmentele sunt fie orizontale (paralele cu axa OX), fie verticale (paralele cu axa OY) şi au capetele în puncte de coordonate întregi. De asemenea, nu există două segmente orizontale situate pe aceeaşi dreaptă şi nici două segmente verticale situate pe aceeaşi dreaptă. Tuturor segmentelor li se poate aplica simultan o operaţie de prelungire la ambele capete cu o valoare întreagă D. Pentru orice segment, dacă lungimea este L, atunci după prelungire dimensiunea sa este L + 2 * D.
Cerinţă
Să se determine valoarea minimă D cu care trebuie prelungite segmentele astfel încât după prelungire segmentele să închidă cel puţin un dreptunghi.
Date de intrare
Pe prima linie a fişierului segmente.in se află un număr natural N reprezentând numărul de segmente. Pe fiecare din următoarele N linii se găsesc câte patru numere întregi x1 y1 x2 y2. Primele două reprezintă un capăt al segmentului, iar ultimele două celălalt capăt.
Date de ieşire
Pe prima linie a fişierului segmente.out, se va scrie un număr natural D reprezentând dimensiunea minimă necesară prelungirii tuturor segmentelor pentru a se forma cel puţin un dreptunghi.
Restricţii
• 4 ≤ N ≤ 1000
• Capetele segmentelor sunt numere întregi din intervalul [-500 000 000, 500 000 000]
• Orice segment are lungimea iniţială de cel puţin 1.
• Pentru datele de intrare, nu există iniţial niciun dreptunghi deja format; de asemenea, vor exista cel puţin 2 segmente verticale şi cel puţin două orizontale
• Se garantează că există o soluţie cu 1 ≤ D ≤ 1 000 000 000
• Pentru 50 % din teste, N ≤ 200
Exemple
segmente.in
segmente.out
Explicaţii
5
1 2 1 3
3 2 4 2
2 3 2 5
5 2 5 7
5 6 7 6
3
Segmentele iniţiale sunt cele îngroşate, cu linie punctată sunt extinderile cu 3 unităţi la ambele capete ale tuturor segmentelor, iar haşurat este marcat dreptunghiul care s-a format după prelungirea cu D = 3.
