Завдання № 1
відбірково-тренувальних зборів
команди міста Києва

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».

Приклад

rectang.inrectang.out
2 3 2 5 3 7 3

0 0 1 1 2 0 2 0
0 0 2 0 5 0 1 1

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

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

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

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

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

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

Приклад

riman2.inriman2.out
90 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 00.028571428

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

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

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

Для векторів b(b1; b2; b3) і c(c1; c2; c3) векторний добуток a = b × c має такі координати:

a1 = b2c3b3c2,
a2 = b3c1b1c3,
a3 = b1c2b2c1.