Fişierul intrare/ieşire:segmente.in, segmente.outSursăONI 2011 - clasa a 10-a
AutorDan PracsiuAdăugată deSpiderManSimoiu Robert SpiderMan
Timp execuţie pe test0.375 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Segmente

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.

  • 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

Exemplu

segmente.insegmente.outExplicaţie
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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content