Submit solution


Points: 1
Time limit: 1.0s
Memory limit: 552M

Problem type

Kao nagradu za izuzetan uspeh na prvom krugu kvalifikacija, Aleksa je dobio na poklon parče keksa u obliku pravougaonika dimenzija W \times H, i postavio ga je u ravan tako da mu se temena nalaze na koordinatama (0, 0), (W, 0), (W, H) i (0, H). Njegov arhineprijatelj Pavle se nameračio na ovo parče keksa i planira da ga pojede. Pavletova vilica se može opisati krugom poluprečnika R. Tokom i-tog minuta desi se jedan od sledeća dva događaja:

  • 1 x_i y_i: Pavle pozicionira svoju vilicu tako da se centar kruga nalazi u tački sa koordinatama (x_i, y_i), zatim grize keks odnosno uklanja sav sadržaj keksa koji se nalazi u njegovoj vilici,

  • 2 x_i: Aleksa uzima lenjir, postavlja ga tako da bude paralelan sa y-osom, tako da prolazi kroz tačku (x_i, 0) i meri dužinu trenutno preostalog parčeta keksa koje se preklapa sa ivicom lenjira.

Da li možete da predvidite koje rezultate merenja će Aleksa dobiti?

Opis ulaza

U prvoj liniji standardnog ulaza nalaze se četiri prirodna broja, odvojena razmakom: W, H, R, Q. U narednih Q linija, nalaze se dva ili tri broja: 1, x_i, y_i ili 2, x_i, odvojena razmakom, koji opisuju i-ti događaj.

Opis izlaza

Za svaki događaj tipa 2 ispisati jedan realan broj - rezultat odgovarajućeg merenja. Ukoliko je tačno rešenje tog merenja b, a vaš program ispisuje broj a, vaš izlaz će se smatrati tačnim ukoliko važi \frac{|a-b|}{\max(1,b)} \leq 10^{-6}.

Primer 1

Ulaz
3 2 2 5
2 1
1 2 3
2 0
2 1
2 2
Izlaz
2.000000000000
2.000
1.267949192431
1
Objašnjenje primera

Pre nego što je Pavle odgrizao parče keksa, na bilo kojoj x-koordinati bila bi izmerena vrednost H = 2. Nakon što je odgrizao parče keksa, na koordinati x = 0 je dužina 2, na x = 1 je 3 - \sqrt{3} \approx 1.268 a na x = 2 je 1 (videti sliku).

Ograničenja

  • 1 \leq W, H, R, Q \leq 10^5
  • 0 \leq x_i \leq W
  • H \leq y_i \leq H+R

Test primeri su podeljeni u 5 disjunktnih grupa:

  • U test primerima vrednim 10 poena: R = 1.
  • U test primerima vrednim 10 poena: R = 2.
  • U test primerima vrednim 10 poena: Q \times W \leq 10^6.
  • U test primerima vrednim 20 poena: Svaki događaj tipa 2 se javlja nakon svih događaja tipa 1.
  • U test primerima vrednim 50 poena: Bez dodatnih ograničenja.

Napomena

Da biste izbegli probleme sa preciznošću, koristite tipove double ili long double u jeziku C++, i ispisujte rešenje na bar 9 decimala.


Comments

There are no comments at the moment.