Полярні прямокутники#3148

Полярні прямокутники

1 секунда

64 мегабайти

Дуже складна

Вася нещодавно дізнався про полярну систему координат, зокрема про поняття полярного прямокутника. На декартовій площині, якщо провести два концентричних кола із центром у початку координат, область між ними називається кільцем (позначена синім на малюнку). Якщо з початку координат проведено два промені, то площа, яку вони охоплюють при обході від першого до другого у проти-годинниковому напрямку (тобто при зростанні кута), називається кутом (область між цими двома променями, показана зеленим). Полярний прямокутник визначається як перетин кута і кільця (виділений червоним).

Задано декілька полярних прямокутників. Знайдіть площу їхнього перетину. Зауважте, що перетин полярних прямокутників може складатися з кількох частин!

Вхідні дані

У першому рядку задано ціле число $N$ — кількість прямокутників ( $1 \leq N \leq 100000$ 1 \leq N \leq 100000). Наступні $N$ рядків містять описи прямокутників. Кожен прямокутник задається чотирма дійсними числами: $r_{1}$ r_1, $r_{2}$ r_2, $φ_{1}$ \varphi_1, $φ_{2}$ \varphi_2. Тут $r_{1}$ r_1 і $r_{2}$ r_2 — радіуси кіл, що формують кільце ( $r_{1} < r_{2}$ r_1 < r_2), а $φ_{1}$ \varphi_1, $φ_{2}$ \varphi_2 — кути (у радіанах), які утворюють перший і другий промені з віссю $x$ . Площа охоплюється від першого променя до другого у проти-годинниковому напрямку (тобто при зростанні кута), навіть якщо $φ_{1} > φ_{2}$ \varphi_1 > \varphi_2. Усі числа наведені з точністю до шести знаків після коми. Кути належать до напіввідкритого інтервалу $[0, 2 π)$ [0, 2\pi), а радіуси не перевищують $1 0^{6}$ 10^6. Гарантується, що $φ_{1} \neq = φ_{2}$ \varphi_1 \ne \varphi_2.

Вихідні дані

Виведіть одне число — площу шуканого перетину. Ваша відповідь вважається правильною, якщо абсолютна або відносна похибка не перевищує $1 0^{- 6}$ 10^{-6}.

Приклади

Приклад 1