Fişierul intrare/ieşire:h.in, h.outSursăHappy Coding 2007
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test1.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

H

Gigel are N segmente verticale, numerotate de la 1 la N. Un segment K este caracterizat prin valorile XK, YjosK si YsusK. Coordonatele capatului de jos al segmentului K sunt (XK,YjosK), iar coordonatele capatului de sus sunt (XK,YsusK). Gigel vrea sa aleaga doua dintre aceste segmente si sa le "taie" in asa fel incat ambele sa aiba aceeasi valoare pentru Yjos, respectiv pentru Ysus. Presupunand ca segmentele alese sunt A si B, noua valoare a lui Yjos pentru fiecare din cele doua segmente va fi max{YjosA,YjosB}, iar noua valoare a lui Ysus pentru fiecare din cele doua segmente va fi min{YsusA,YsusB}. Sa notam prin YJ valoarea max{YjosA,YjosB} si prin YS valoarea min{YsusA,YsusB}. Daca nu este adevarata relatia YJ ≤ YS, atunci perechea de segmente (A,B) nu este valida (iar Gigel nu ar alege niciodata o pereche invalida). Pentru o pereche valida de segmente (A,B), dupa operatia de "taiere" a segmentelor, el va uni segmentele printr-un segment orizontal, pentru a forma o figura care seamana foarte mult cu litera "H". Segmentul orizontal va fi trasat intre coordonatele (XA,Y) si (XB,Y), cu YJ ≤ Y ≤ YS (nu este importanta valoarea exacta a coordonatei Y a segmentului trasat). Dupa obtinerea literei "H", Gigel calculeaza "lungimea" acesteia. Lungimea literei "H" este definita ca fiind suma celor 3 laturi ale literei: 2*(YS-YJ)+|XB-XA|.

Ajutati-l pe Gigel sa aleaga o pereche valida de segmente pentru care lungimea literei H obtinuite sa fie maxima.

Date de intrare

Prima linie a fisierului de intrare h.in contine numarul intreg contine numarul intreg N, reprezentand numarul de segmente verticale. Fiecare din urmatoarele N linii contine 3 numere intregi, separate prin cate un spatiu: X, Yjos, Ysus (avand semnificatia mentionata anterior). A K-a linie dintre aceste N linii contine valorile ce caracterizeaza al K-lea segment.

Date de iesire

Fisierul de iesire h.out va contine un numar intreg reprezentand lungimea maxima a unei litere H pe care o poate desena Gigel conform procedeului mentionat.

Restrictii

  • 1 ≤ N ≤ 65535
  • Pentru fiecare segment:
    • 0 ≤ X, Yjos, Ysus ≤ 100 000 000
    • Yjos ≤ Ysus
  • Va exista cel putin o pereche valida de segmente.

Exemplu

h.inh.out
2
0 0 10
5 5 20
15
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content