segmente

Segmente

== include(page="template/taskheader" task_id="segmente") ==

Poveste şi cerinţă...

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.

h2. Date de intrare

Fişierul de intrare $segmente.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $segmente.out$ ...
 
h2. Restricţii

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.

* $... ≤ ... ≤ ...$

* $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 |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

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

== include(page="template/taskfooter" task_id="segmente") ==

5594