1.1. Прямокутник (оптимізований перебір)

1. Перевірити, чи сума площ прямокутників для склеювання дорівнює площі останнього прямокутника;

2. Перевірити, чи прямокутники для склеювання можна розташувати всередині останнього прямокутника;

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

1.2. Геометрiя Рiмана-2 (аналітична геометрія)

1. Перейти до декартових координат вершин ламаної.

2. Використовуючи подвійний векторний та скалярний добутки, визначити внутрішні кути криволінійного многокутника з використанням центру кулі як точки спостереження.

3. Знайти площу многокутника як добуток квадрата радіуса земної кулі на різницю суми внутрішніх кутів та добутку числа Піфагора π на кількість вершин, зменшену на 2.

Дамо детальний опис математичної моделі.

Означення 1. Кажуть, що вектор a є векторним добутоком неколінеарних векторів b і c (це позначають a = b × c), якщо:

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

Теорема 1. Для векторів a(a₁; a₂; a₃), b(b₁; b₂; b₃), c(c₁; c₂; c₃), рівність a = b × c еквівалентна системі таких рівностей:

Доведення поданої теореми можна знайти у підручнику з аналітичної геометрії. Наприклад, див. О.Рудик, Початки алгебри, аналізу, аналітичної геометрії та теорії ймовірностей. — Тернопіль: Навчальна книга — Богдан, 2005. 416 с.

Перехід від ґрадусної міри (g ґрадусів m мінут s секунд) до радіанної (φ радіан) здійснюють згідно з такою формулою:

Позначимо через (r; θ; φ ) сферичні координати точок простору:
r — відстань від центру Землі до даної точки;
θ — широта, що змінюється у межах від π /2 до π /2;
φ — довгота, що змінюється у межах від – π до π.

Маємо:
x = r cos θ cos φ;
y = r cos θ sin φ;
z = r sin θ.

Не обмежуючи загальності міркувань, за одиницю довжини виберемо довжину радіуса Землі.

Запровадимо такі позначення:

• n — кількість вершин контура, утвореного на поверхні Землі меншими дугами кіл з центром у центрі Землі;

• A₁, A₂, …, A_n — послідовні вершини цього контура;

• v₁, v₂, …, v_n — вектори зі спільним початком у центрі Землі, що є початком прямокутної декартової системи координат, і кінцями відповідно у точках A₁, A₂, …, A_n;

• v₀ = v_n, v_{n + 1} = v₁.

Частину сфери, обмежена контуром, можна розбити на (n – 2) криволінійних трикутники. Алгоритм такого розбиття — окреме питання, яке тут не розглянуто. Площа такого криволінійного трикутника дорівнює добутку квадрата радіуса сфери й різниці суми внутрішніх кутів і числа π. В умові завдання це твердження було подано без доведення. Таким чином, задачу зведено до пошуку суми внутрішніх кутів контура.

Запровадимо такі позначення:

• u_j = (v_j × v_{j – 1}) × v_j — вектор, дотичний до дуги A_j A_{j – 1} у точці A_j, бо
  u_j ⊥ v_j,    u_j ⊥ v_j × v_{j – 1},    v_j ⊥ v_j × v_{j – 1},    v_{j – 1} ⊥ v_j × v_{j – 1};


• w_j = (v_j × v_{j + 1}) × v_j — вектор, дотичний до дуги A_j A_{j + 1} у точці A_j, бо
  w_j ⊥ v_j,    w_j ⊥ v_j × v_{j + 1},    v_j ⊥ v_j × v_{j + 1},    v_{j + 1} ⊥ v_j × v_{j + 1}.

Шуканий кут — це кут від напряму u_j до напряму w_j з точок зору (спостереження), розташо­ваних по один бік від сфери. За таку єдину точку зору для всіх внутрішніх кутів контура візьмемо центр сфери. Для цього розглянемо додатно орієнтовану локальну систему координат з початком у A_j і векторами бази, що однаково спрямовані відповідно з векторами v_j , u_j і v_j × u_j.

Вектор w_j лежить у площині, що паралельна до векторів u_j і v_j × u_j. З допомогою скалярного добутку можна знайти косинуси кутів між цими векторами й вектором w_j. Знаючи ці косинуси, можна знайти кут від напрямку u_j до напрямку w_j.

Математична модель дозволяє проводити розрахунки без запам'ятовування координат усіх вершин контура, бо достатньо зберігати в оперативній пам'яті координати лише трьох послідовних вершин.