Sparing w Programowaniu Politechnika Poznańska, 24.02.2007

Opis

Kiedy światło przechodzi przez błonę fotograficzną część energii jest pochłaniane, a reszta przenoszona na drugą stronę filmu. Procent światła, który jest przenoszony może być zdefiniowany jako współczynniki przepuszczalności.

Kiedy kilka błon znajdzie się na drodze tego samego promienia światła, współczynniki przepuszczalności mnożą się. Celem tego zadania jest określenie ilości światła (w procentach), która dociera do ziemi, po przejściu przez kolejne zestawy filmów.

Rozważmy zbiór odcinków na rysunku 1. Reprezentują one błony fotograficzne według zdefiniowanych powyżej warunków (współczynniki przepuszczalności zapisane w nawiasach). Załóżmy również, że światło porusza się w pionie z góry do dołu.

Na rysunku punkty końcowe odcinków wyznaczają na podłożu zbiór odcinków (podłoże jest reprezentowane przez oś X). Dla każdego takiego odcinka, możliwe jest obliczenie ilości światła, która dociera do podłoża. Dla całego danego zbioru można wyznaczyć następującą listę:

-inf, 2.0 -> 1.000
2.0, 4.0 -> 0.900
4.0, 7.0 -> 0.630
7.0, 9.0 -> 0.504
9.0, 13.5 -> 0.560
13.0, 17.0 -> 0.800
17.0, +inf -> 1.000

Dla uproszczenia tego problemy zakładamy, że żaden odcinek filmu nie jest pionowy i fragmenty poszczególnych filmów nie przecinają się. Dodatkowo żadne dwa punkty w projekcji pionowej na podłoże nie mają takiego samego położenia (innymi słowy współrzędne X każdego punktu końcowego odcinków są różne). Z drugiej strony, współrzędna może być dowolną wartością od -inf do +inf.

Specyfikacja wejścia

W pierwszej linii wejścia podana będzie liczba d (1 ≤ d ≤ 50) określająca liczbę przypadków testowych.

Każdy przypadek testowy rozpoczyna się linią zawierającą liczbę całkowitą n (1 ≤ n ≤ 2*10⁴) będącą liczbą odcinków. W kolejnych liniach zdefiniowane są kolejne odcinki w formacie x1 y1 x2 y2 r - gdzie x1 y1 x2 y2 określają współrzędne końców odcinka (0 ≤ x, y ≤ 10⁹), zaś r jego współczynnik przepuszczalności (0 < r ≤ 1).

Specyfikacja wyjścia

Dla każdego przypadku w pierwszej linii powinna znaleźć się liczba k odcinków powstałych w wyniku projekcji punktów. W kolejnych liniach następują opisy kolejnych odcinków (współrzędne X1 X2) wraz z ilością światła, które do nich dociera. Wszystkie wartości powinny być wyrażone liczbą rzeczywistą zaokrągloną do 3 miejsc po przecinku. Wielkości nieskończone muszą być reprezentowane przez '-inf' lub '+inf'.

Przykład

1
3
2.000 2.000 9.000 2.000 0.900
13.500 2.000 4.000 8.500 0.700
17.000 10.000 7.000 8.500 0.800

7
-inf 2.000 1.000
2.000 4.000 0.900
4.000 7.000 0.630
7.000 9.000 0.504
9.000 13.500 0.560
13.500 17.000 0.800
17.000 +inf 1.000