Условие: Номер 23

Задача 23. Нижняя левая и верхняя правая вершины прямоугольника A имеют координаты (0,0) и (V,W) соответственно. Множество S из N точек задается парами координат (x[i],y[i]), 1<=i<=N. Найти такой прямоугольник G максимальной площади, что его стороны параллельны сторонам A, G полностью лежит в A (G и A могут иметь общие граничные точки) и ни одна точка из S не лежит внутри G (но может лежать на его стороне). Напечатать величину площади G и координаты нижней левой и верхней правой вершин этого прямоугольника. Если таких прямоугольников несколько, то вывести информацию по каждому. Замечание: в множестве S никакие две точки не лежат на одной прямой, параллельной стороне A. Необходимо: 1. Организовать ввод данных в виде < Введите V и W -- координату верхней правой вершины прямоугольника A > < Введите N -- число точек > < Введите координаты точек > x[1]--> y[1]--> ..... x[N]--> y[N]--> 2. Вывести результаты в виде < Максимальная площадь прямоугольника = > < Координаты нижней левой и верхней правой вершин прямоугольника(ов) > x1--> y1--> x2--> y2-->

  Решение задачи: Номер 23

Решение задачи 23. Считаем, что точки в S не дублируется (т.к. S - множество). Введем в множество S точки (0,W),(0,0),(V,0),(V,W) - вершины A. Пусть есть два двумерных массива - BX и BY; в массиве BX располагаются координаты точек множества S в порядке неубывания абсциссы, в BY - по невозрастанию ординаты. Будем считать, что BX[i,1] и BX[i,2] (аналогично BY[j,1] и BY[j,2]) соответственно x и y-координаты точки из S. Рассмотрим множество прямоугольников Pi, удовлетворяющих условию задачи. Тот из них, который имеет максимальную площадь и является искомым. Очевидно, что на каждой из сторон Pi должна лежать точка из S, либо сторона Pi должна лежать на стороне A. Рассмотрим следующие случаи: 1) Верхняя сторона P лежит на верхней стороне прямоугольника A. Для каждой точки BX[i] ищем, двигаясь по массиву BX вправо и влево от элемента BX[i] такие первые BX[j] и BX[k], j<i, k>i, что BX[j,2]>BX[i,2], BX[k,2]>BX[i,2]. Считаем, что стороны прямоугольника Pi проходит: нижняя - через точку BX[i], левая - через BX[j], правая - через BX[k]. Верхняя сторона лежит на верхней стороне A. Таким образом находим все прямоугольники, примыкающие к верхней стороне. Прямоугольники, примыкающие к нижней, левой и правой сторонам A находятся аналогично, но в двух последних случаях надо вместо BX использовать массив BY. 2) Случай, когда ни одна из сторон Pi не лежит на стороне A. Берем последовательно точки массива BY[i], i=1, ..., N, и считаем, что верхняя сторона Pi проходит через точку BY[i]. Для этой точки полагаем сначала, что XBegin=0, XEnd=V. Находим такие точки BY[j] и BY[k] (при просмотре массива BY вправо от элемента BY[i]), что BY[j,2]<BY[i,2], BY[k,2]<BY[i,2], BY[j,1]<=XBegin, BY[k,1]<=XEnd, BY[j,1]<BY[i,1], BY[k,1]>BY[i,1] (объяснение смотрите ниже), т.е. мы находим точки с максимальной ординатой, через которые можно провести правую и левую стороны прямоугольника Pi). Внутри интервала (BY[j,1], BY[k,1]) на оси OX ищем точку BY[l,1] такую, что y - координата этой точки BY[l,2] максимальная, меньшая величины max{BY[j,2],BY[k,2]}. Через эту точку BY[l] будем проходить нижняя сторона прямоугольника. Полагаем XBegin=BY[j,1], XEnd=BY[k,1]. Но этим прямоугольником может не исчерпываться все множество прямоугольников, у которых точка BY[i] лежит на верхней стороне. Попытаемся найти еще один из таких прямоугольников. Очевидно, что левая его сторона имеет x-координату не меньшую, чем XBegin, а правая - не большую, чем XEnd. Будем искать такую точку BY[l], что XBegin<=BY[l,1]<=XEnd (теперь уже понятно почему), BY[l,2] максимальная из всех ординат, меньших max{BY[j,2],BY[k,2]} (мы "сужаем" прямоугольник как можно незначительнее). Если BY[l,1]<BY[i,1], то это новая левая сторона, иначе - новая правая. Находим новую нижнюю сторону, и т.д. Если мы не можем найти нового BY[l], то просмотр прямоугольников с точкой BY[i] на верхней стороне закончен, и мы переходим к BY[i+1].

Назад