Datorită tehnologiei de ultimă generaţie este posibilă controlarea vremii. De exemplu, pentru a preveni ploaia, se trimite de pe pământ o rază specială care să "anihileze" norii de pe cer. Raza va anihila toţi norii pe care îi intersectează. Meteorologul de serviciu a observat în această dimineaţă un cer noros, pe care sunt N nori. Norii pot fi consideraţi paraleli cu pământul, meteorologul cunoscând pentru fiecare nor înălţimea la care se află şi poziţia exactă faţă de orizontală (pentru această problemă, se va considera că norii sunt statici). Meteorologul vrea să aleagă o poziţie de pe pământ din care să poată trimite o rază (verticală sau diagonală) care să anihileze cât mai mulţi nori.
Din punct de vedere formal, se dau N segmente paralele cu axa Ox şi trebuie să se determine o semidreaptă cu capătul pe Ox care să intersecteze cât mai multe segmente din cele date.
Cerinta
Scrieţi un program care să determine numărul maxim de nori care pot fi anihilaţi.
Date de intrare
Fişierul de intrare nori.in conţine pe prima linie un singur număr natural N, reprezentând numărul de nori. Fiecare dintre următoarele N linii conţine un triplet de numere întregi (h x1 x2), semnificând că există un nor la înălţimea h, între abscisele x1 şi x2.
Date de iesire
Fişierul de ieşire nori.out va conţine pe prima linie numărul maxim de nori care pot fi anihilaţi. A doua linie va conţine abscisa minimă de unde poate fi trimisă o rază care să anihileze numărul maxim de nori.
Restrictii
1 <= N <= 1 000
Pentru fiecare nor reprezentat de tripletul (h x1 x2), 0 < h, |x1|, |x2| <= 30000şi x1 < x2
Un nor se consideră intersectat inclusiv dacă este intersectat în unul dintre capete
Nu va exista o semidreaptă care să aibă capătul pe Ox şi care să conţină 3 capete de nori
Nu vor exista nori care se intersectează.
Vor exista cel puţin 2 nori situaţi la înălţimi diferite.
Abscisa afisata va fi considerata corecta daca diferenta in valoare absoluta intre abscisa afisata si cea corecta este <=0.01.
Exemplu
nori.in
nori.out
4
3 7 8
1 6 10
4 1 3
3 3 5
3
7.0000
Filip Cristian Buruiana
stud. Facultatea de Automatica si
Calculatoare, Universitatea Politehnica, Bucuresti