== include(page="template/taskheader" task_id="segmente") ==
p<>. 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$.
h2. 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.
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$.
h2. 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.
Fişierul de intrare $segmente.in$ ...
h2. 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.
În fişierul de ieşire $segmente.out$ ...
h2. Restricţii
* $4 ≤ N ≤ 1 000$
* 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$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. segmente.in |_. segmente.out |_. Explicaţie |
| 5
1 2 1 3
3 2 4 2
2 3 2 5
5 2 5 7
5 6 7 6
| 3
| !<problema/segmente?p1.jpg! 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$.
|
table(example). |_. segmente.in |_. segmente.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="segmente") ==
