1. Прямокутник

Максимальна оцінка: 48 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: rectang.in
Вихідний файл: rectang.out
Програма: rectang.*

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

Вхідні дані
Файл rectang.in містить натуральне число n, n < 15, а далі — послідовність (n + 1)-ої пари натуральних чисел, що є довжинами й висотами відповідних прямокутників. Площі всіх прямокутників не перевищують 1234567890.

Вихідні дані
Розташуємо (n + 1)-ий прямокутник таким чином, щоб початок координат був вершиною прямокутника, одна сторона-висота належала осі ординат, а всі внутрішні точки лежали у першій чверті декартової площини. Кожний рядок файлу rectang.out має містити n четвірок невід'ємних цілих чисел, що взаємно однозначно описують відповідне склеювання.

Перші два числа такої четвірки — це координати нижньої лівої вершини прямокутника, третє число — його номер, останнє число — 1 або 0 відповідно до того, чи повернуто на 90° цей прямокутник, чи ні.

Рядки rectang.out потрібно записати в лексикографічному порядку, а в кожному рядку четвірки чисел також потрібно розташувати у лексикографічному порядку.

Якщо склеювання неможливе, то файл rectang.out має містити два слова: «No solution».

Приклад

2. Геометрія Рімана-2

Максимальна оцінка: 32 бали
Обмеження на час: 1 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: riman2.in
Вихідний файл: riman2.out
Програма: riman2.*

На поверхні Землі послідовність точок сполучено меншими дугами кіл з центром у центрі Землі, а останню точку з'єднано з першою. Відомо, що утворений таким чином контур не має самоперетину.

Завдання
Створіть програму riman2.*, яка обчислить площі фіґур, обмежених контуром.

Вхідні дані
Файл riman2.in містить шістки цілих чисел — координати вказаних точок у порядку обходу контура: ґрадус, мінута й секунда широти, ґрадус, мінута й секунда довготи. Якщо точка знаходиться у південній (західній) півкулі, то всі відповідні координати широти (довготи) вказано із знаком «–».

Вихідні дані
Файл riman2.out містить запис з точністю до 9 знаків після десяткової крапки відношення площ фіґур (меншої до більшої), на які контур поділяє поверхню Землі.

Приклад

Математична довідка
Площа сфери з радіусом r дорівнює 4πr².

Площа криволінійного трикутника, утвореного на цій сфері меншими дугами кіл з центром у центрі сфери, дорівнює (A + B + C – π) r², де
A, B, C — кути між дотичними до дуг, проведених у точці їх перетину,
π = 3,14159265358979323846… — число Піфагора — відношення довжини кола до його діаметра.

a є векторним добутком векторів b i c (позначают a = b × c), якщо:

• | a | = | b | · | c | · sin φ, де φ — кут між векторами b i c;
• a ⊥ b i a ⊥ c;
• трійка векторів a, b i c має додатну орієнтацію.

Для векторів b(b₁; b₂; b₃) і c(c₁; c₂; c₃) векторний добуток a = b × c має такі координати: