Tsubasa-chan adoră dulciurile! De curând a apărut un nou tip de desert. Astfel decide să înfăptuiască o nouă fabrică care să producă acest produs delicios. Fabrica conține un container imens pătratic, plin de aluat, de 10
6
x 10
6
unități. Fiecare punct din container are drept coordonate o pereche de numere reale (x, y)
, unde 0 ≤ x, y ≤ 10
6
, iar fiecare punct are o dulceață. Dulceața unui punct este un număr real, inițial 0
. Pentru fabricarea desertului este nevoie de Q
operații, care pot fi de următoarele tipuri:
- O îndulcire verticală, determinată de o coordonată
x
u
întreagă și o valoare întreagăv
. După această operație, toate punctele din container(x, y)
undex
u
≤ x < x
u
+ 1
devin mai dulci cuv
. - O îndulcire orizontală, determinată de o coordonată
y
u
întreagă și o valoare întreagăv
. După această operație, toate punctele din container(x, y)
undey
u
≤ y < y
u
+ 1
devin mai dulci cuv
. - O degustare, determinată de 4 coordonate întregi
x
q
,y
q
,x
q'
,y
q'
. Pentru aceeastă operație, Tsubasa ia o lingură, o pune în aluat la punctul(x
q
,y
q
)
, și apoi o duce in linie dreaptă la punctul(x
q'
,y
q'
)
. Mișcarea se efectuează într-o secundă, cu viteză constantă. După aceea, Tsubasa gustă desertul, vrând să afle dulceața totală a aluatului din lingură. Această valoare se calculează în felul următor: dacă lingura trece prin zone de dulceațad
1
pentrut
1
secunde, de dulceațăd
2
pentrut
2
secunde, …, și de dulceațăd
k
pentrut
k
secunde, atunci dulceața totală din lingură estet
1
•d
1
+t
2
•d
2
+ … +t
k
•d
k
. Nu se modifică dulceața din container.
Cerința
Dându-se toate operațiile întreprinse în producerea desertului, să se găsească dulcețurile totale ce sunt găsite la toate operațiile de degustare.
Date de intrare
Pe prima linie a fișierului de intrare dulciuri.in se va găsi numărul Q
de operații.
Pe următoarele Q
linii urmează descrieri a tuturor operațiilor, câte una pe linie, în ordine. O operație este codificată în felul următor:
- O îndulcire verticală este codificată prin
1 x
u
v
. - O îndulcire orizontală este codificată prin
2 y
u
v
. - O degustare este codificată prin
3 x
q
y
q
x
q'
y
q'
.
Date de ieșire
În fișierul de ieșire dulciuri.out
, să se afișeze toate rezultatele degustărilor, în ordine, câte una pe linie. Rezultatul unei degustări se consideră a fi corect daca eroarea absolută sau relativă față de soluția comisiei este cel mult 10
-7
.
Restricții și precizări
- Toate coordonatele din datele de intrare sunt întregi în intervalul
[0, 1.000.000]
. 0 ≤ v ≤ 1000
.v
este întreg.1 ≤ Q ≤ 100.000
.- Pentru 20 de puncte nu se fac îndulciri orizontale și
Q ≤ 2000
. - Pentru 20 de puncte, la fiecare degustare, fie
x
q
= x
q'
sauy
q
= y
q'
,Q ≤ 2000
- Pentru 10 de puncte, se face cel mult o degustare
- Pentru 20 de puncte, toate degustările se fac după toate îndulcirile
- Pentru 10 de puncte,
Q ≤ 2000
- Pentru 20 de puncte, fără restricții suplimentare
Exemplul 1:
dulciuri.in
3 1 2 60 2 3 60 3 0 0 3 4
dulciuri.out
35
Explicație
Situația pentru degustarea din primul exemplu este explicată în diagrama de mai jos.
Zonele roz sunt zonele în care s-a aplicat o îndulcire, și numerele reprezintă cu cât s-a îndulcit. Zona din intersecția îndulcirilor are dulceața 120. Linia diagonală punctată reprezintă traseul.
Traseul are lungimea \( \sqrt{3^2 + 4^2} = 5 \), și este completat într-o secundă – astfel are viteza de 5
unități pe secundă. Segmentul de la (2, 2.(6))
la (2.25, 3)
are lungimea \( \sqrt{(2.25 – 2)^2 + (2.(6) – 3)^2} = \sqrt{¼^2 + (1/3)^2} = 5/12 \), și are dulceața 60
– astfel el este traversat în (5/12) x (1/5) = 1/12
secunde, și contribuie cu (1/12) x 60 = 5
la dulceața totală. Segmentul de la (2.25, 3)
la (3, 4)
are lungimea \( \sqrt{(3 – 2.25)^2 + (4 – 3)^2} = 5/4 \), și are dulceața 120
– astfel el este traversat în (5/4) x (1/5) = 1/4
secunde, și contribuie cu (1/4) x 120 = 30
la dulceața totală. Astfel, cum segmentul de la (0, 0)
la (2, 2.(6))
contribuie cu 0
, dulceața totală este 35
.
Exemplul 2:
dulciuri.in
4 1 2 10 3 2 0 2 1 3 3 0 3 1 3 2 0 2 0
dulciuri.out
10 0 10
Explicație
Situația pentru degustările din al doilea exemplu este explicată în diagrama de mai jos.
În primul traseu (cel din stânga) trecem mereu printr-o zonă cu dulceața 10
, deci rezultatul degustării este 10
. În al doilea traseu (cel din dreapta) trecem mereu printr-o zonă cu dulceața 0
, deci rezultatul degustării este 0
. În al treilea traseu, stăm pe loc pentru o secundă într-o zona de dulceață 10
, deci răspunsul este 10
.
Exemplul 3:
dulciuri.in
6 1 4 413 1 3 234 2 5 244 2 3 777 3 1 2 14 15 3 31 4 2 40
dulciuri.out
128.3076923077 29.0881226054