Задача 14.
Прямоугольник ABCD задан координатами своих вершин. На противоположных сторонах AB и CD заданы последовательности R1 и R2 из N точек разбиения, а на сторонах BC и AD - R3 и R4 из M точек разбиения. Нумерация элементов последовательности R1 и R2 начинается соответственно от точек A и D, а в R3 и R4 -- от B и A. Соединив отрезками точки с одинаковыми номерами в разбиениях R1 и R2, а затем в разбиениях R3 и R4, получим разбиение Q прямоугольника ABCD на множество четырехугольников. Построить алгоритм, определяющий четырехугольник разбиения Q с наибольшей площадью, при условии, что отрезки, соединяющие точки разбиений R1 и R2 параллельны стороне AD. Последовательности R1, R2, R3 и R4 задаются как массивы из длин отрезков разбиения соответствующих сторон прямоугольника.
|
Решение задачи 14.
Отрезки, соединяющие точки разбиения R1 и R2, параллельны стороне AD. Будем брать отрезки, соединяющие последовательные точки разбиения R3 и R4 и искать между этими двумя последовательными отрезками четырехугольник с наибольшей площадью. Четырехугольник разбиения Q с максимальной площадью есть четырехугольник с максимальной площадью по всем таким разбиениям прямоугольника отрезками.
Пусть последовательные точки разбиения с одинаковыми номерами
на сторонах BC и AD есть, соответственно f1,f2 и g1,g2.
Если f2-f1=g2-g1, то анализируемые четырехугольники есть параллелепипеды, и параллелепипед с максимальной площадью определяется максимальной длиной отрезка в разбиении R1 (или, что то же, R2).
Если, для определенности f2-f1 > g2-g1 (случай обратного неравенства рассматривается аналогично), то, обозначая f2-f1=h1, g2-g1=h2, l=CD, h' и h" - соответственно высоты левой и правой сторон четырехугольника, L2 - ширину его основания, z - точку пересечения продолжения верхней и нижней сторон четырехугольника, L1, L3 и x - соответственно расстояния от левой стенки прямоугольника ABCD до четырехугольника, от правой стенки прямоугольника ABCD до четырехугольника, от точки x до прямоугольника ABCD, площадь четырехугольника - s; получаем следующую схему и равенства:
Для каждой пары отрезков, определяемых точками разбиения R3 и R4, находим максимальную площадь четырехугольника между этими двумя отрезками.
|
