 |
Выпуклая оболочка множества N точек плоскости
|
|
|
|
Геометрические задачи на олимпиадах по информатике
Исполнитель: Студентка группы М-31
Селиванцова А.Ю.
Научный руководитель:
Канд. физ-мат. наук, доцент Лебедева М.Т.
Гомель 2007
Содержание
Введение
1. Основные формулы и алгоритмы
2. Численное решение геометрических задач
3. Различные задачи
Заключение
Литература
Введение
На большинстве многих областных олимпиадах по информатике по крайней мере одна из задач связана с геометрическими понятиями. Причем сформулированы они чаще всего в терминах вычислительной геометрии и описание таких объектов как прямая, отрезок, окружность, треугольник и т.д. производится путем задания координат точек, характеризующих эти объекты, в той или иной системе координат. Прежде, чем мы перейдем к рассмотрению этого класса олимпиадных задач, перечислим элементарные подзадачи (иногда это просто формулы из курса математики), на решение которых обычно опираются решения задач вычислительной геометрии.
Основные формулы и алгоритмы
Большинство из перечисленных задач либо не требуют пояснений, либо приведены в [1-4]. Напомним лишь наиболее важные из них. Причем основным инструментом для построения наиболее простых формул во многих задачах вычислительной геометрии является векторное произведение. Поэтому рассмотрение начнем с вопросов, с ним связанных.
Косое произведение в задачах вычислительной геометрии
Под косым произведением векторов p 1 и p 2 с декартовыми координатами (x 1, y 1) и (x 2, y 2) можно понимать ориентированную площадь параллелограмма, образованного точками (0,0), (x 1, y 1), (x 2, y 2), (x 1 + x 2, y 1 + y 2), которая равна p 1´ p 2 = – p 2´ p 1= x 1 y 2 – x 2 y 1 (задача 5.5). Косое произведение напрямую связано с понятием векторного произведения (но в отличие от последнего это скаляр). Поэтому в литературе по вычислительной геометрии иногда используется именно ито понятие. По-другому косое произведение как и векторное обозначается [ p 1, p 2]. Если два вектора провести из общей начальной точки, то их косое произведение больше нуля, если угол между первым и вторым вектором ориентирован также как угол между первым и вторым базисными векторами и меньше нуля — в противном случае. Косое произведение ненулевых векторов равно нулю тогда и только тогда, когда они коллинеарны (сонаправлены или противоположно направлены).
|
|
|
В задаче 3.2 проверить наличие пересечения у двух отрезков (а зачастую нас интересует лишь сам факт пересечения) несложно именно с использованием косого произведения. Пусть первый отрезок задан точками p 1 и p 2, а второй — p 3 и p 4 (также обозначаются вектора с соответствующими координатами). Обозначим xmax 1 и xmin 1 — максимальную и минимальную из первых координат первого отрезка, xmax 2 и xmin 2 — то же для второго отрезка. Для второй координаты аналогично имеем ymax 1, ymin 1, ymax 2 и ymin 2. Упомянутые отрезки пересекаются тогда, когда
а) пересекаются ограничивающие их прямоугольники, т.е. xmax 1 ³ xmin 2, xmax 2 ³ xmin 1, ymax 1 ³ ymin 2 и ymax 2 ³ ymin 1;
б) косые произведения (p 3 – p 1)´(p 2 – p 1) и (p 4 – p 1)´(p 2 – p 1) имеют разный знак, точнее
[(p 3 – p 1),(p 2 – p 1)]×[(p 4 – p 1),(p 2 – p 1)] £ 0;
в) [(p 1 – p 3),(p 4 – p 4)]×[(p 2 – p 3),(p 4 – p 3)] £ 0.
Последние два условия означают, что концы одного отрезка лежат по разные стороны от прямой, которой принадлежит другой отрезок. Первое же условие исключает из специального рассмотрения случай равенства нулю всех четырех косых произведений, при котором отрезки лежат на одной прямой и могут как пересекаться, так и нет.
Площадь треугольника (задача 6.3) равна половине модуля косого произведения двух векторов, образованных любыми двумя его сторонами.
|
|
|
Тогда расстояние от точки C до прямой, заданной координатами точек A и B (задача 4.2), можно подсчитать как отношение модуля косого произведения векторов CA и CB к длине отрезка AB (данная формула следует из двух способов вычисления площади треугольника).
Площадь произвольного многоугольника с вершинами p 0, p 1, …, pn -1, перечисленными в порядке его обхода против часовой стрелки, (задача 6.4) можно вычислить как сумму ориентированных площадей треугольников, образованных векторами pi и pi +1, i = 0, …, n – 1; i + 1 вычисляется по модулю n.
Выпуклость многоугольника (задача 6.2) с вершинами p 0, p 1, …, pn -1, перечисленными в порядке его обхода, легко проверить с помощью сравнения знаков косого произведения пар векторов (pi +1 – pi) и (pi +2 – pi +1), i = 0, …, n – 1; i + 1 и i + 2 вычисляются по модулю n. В случае выпуклого многоугольника знаки у всех указанных произведений совпадают (если мы знаем направление обхода, то знак косых произведений для выпуклого многоугольника определен: при обходе по часовой стрелке произведения отрицательны, а против часовой стрелки — положительны).
На этом способы полезного применения косого произведения отнюдь не исчерпаны.
Выпуклая оболочка множества N точек плоскости
Задача состоит в том, чтобы перечислить все точки, принадлежащие границе выпуклой оболочки заданного множества точек, в порядке ее обхода, например, против часовой стрелки (в некоторых задачах требуется перечислить только угловые точки). Для эффективного решения этой задачи существует несколько различных алгоритмов (см. [1]-[4]). Приведем наиболее простую реализацию одного из них — алгоритма Джарвиса.
{ следующий абзац проиллюстрировать рисунком из номера 16/2000, стр. 11 }
Перечисление точек искомой границы выпуклого многоугольника начнем с правой нижней точки, которая заведомо принадлежит границе выпуклой оболочки. Обозначим ее координаты (x 0, y 0). Следующей, при указанном порядке обхода, будет точка (x 1, y 1), для которой угол между осью OX и вектором (x 0, y 0)‑(x 1, y 1) минимален. Если таких точек несколько, то угловой в многоугольнике станет точка, для которой длина вектора (x 0, y 0)‑(x 1, y 1) максимальна, а следующей точкой, принадлежащей выпуклой оболочке — та, длина вектора у которой минимальна (таким образом наш выбор будет зависеть от конкретной постановки задачи). Для нахождения следующей точки значения углов между векторами вычислять необязательно. Мы опять можем воспользоваться понятием знака векторного произведения. Пусть, далее, мы уже нашли i ‑ю вершину выпуклой оболочки (xi, yi). Тогда, (i + 1)-я точка есть такая точка, еще не вошедшая в выпуклую оболочку, для которой угол между вектором (xi ‑1, yi ‑1)‑(xi, yi) и вектором (xi, yi)‑(xi +1, yi +1) минимален, при минимальной длине вектора (xi, yi)‑(xi +1, yi +1) среди всех векторов с таким углом. Заметим, что для всех остальных точек (x, y), вектор (xi, yi)‑(x, y) будет лежать вне угла, образованного указанными векторами, левее него. Тогда векторное произведение (xi +1 – xi)(y – yi) – (yi +1 – yi)(x – xi) ³ 0, для любой точки (x, y), еще не вошедшей в границу выпуклой оболочки. Следовательно, мы можем сначала считать следующей, (i + 1)‑ой, любую, еще не вошедшую в выпуклую оболочку, точку, а затем, вычисляем указанное выражение для остальных “свободных” точек (х, y). Если для одной из них (xi +1 – xi)(y – yi) – (yi +1 – yi)(x – xi) < 0, считаем следующей ее и продолжаем проверку остальных точек (аналогично алгоритму поиска минимального элемента в массиве). Если же значение выражения равно 0, то сравниваем квадраты длин векторов, а именно (xi +1 – xi)2 + (yi +1 – yi)2 и (x – xi)2 + (y – yi)2.
|
|
|
Таким образом, при решении данной задачи в случае изначально целочисленных координат мы полностью можем избежать применения вещественной арифметики, а, следовательно, избавиться от потери точности вычислений. В противном случае, в решение могут быть включены “лишние” точки, близкие к границе выпуклой оболочки или не учтены некоторые из “нужных” точек. Сложность данного алгоритма составит O (kN), где k — количество точек в выпуклой оболочке, в худшем случае равное N. Существуют алгоритмы решения этой задачи, основанные на предварительной сортировке точек исходного множества, например, по значению угла в полярной системе координат с центром в одной из точек выпуклой оболочки, с вычислительной сложностью O (N log N) (алгоритм Грехема). То есть наиболее трудоемкой задачей оказывается именно сортировка исходных точек.
|
|
|
Приведем программу решения данной задачи алгоритмом Джарвиса:
var a, b: array [1..100] of record
x,y: integer;
f: boolean
end;
min, m, j, k, n: integer;
Begin
readln(n);
for i:=1 to n do
Begin
read(a[i].x, a[i].y);
a[i].f:= false
end;
{ищем нижнюю правую точку}
m:=1;
for i:=2 to n do
if a[i].y < a[m].y then m:=i else
if (a[i].y = a[m].y) and
(a[i].x > a[m].x) then m:=i;
b[1]:=a[m];
a[m].f:= true;
k:=1;
Repeat
min:=1;
{ищем первую еще свободную точку}
while a[min].f do inc(min);
{ищем очередную вершину выпуклой оболочки}
for j:=1 to n do
if (not a[j].f) and
((a[min].x-b[k].x)*(a[j].y-b[k].y)-
(a[j].x-b[k].x)*(a[min].y-b[k].y)<0)
then min:=j else
if (not a[j].f) and
((a[min].x-b[k].x)*(a[j].y-b[k].y)-
(a[j].x-b[k].x)*(a[min].y-b[k].y)=0) and
(sqr(a[min].x-b[k].x)+sqr(a[min].y-b[k].y) >
sqr(a[j].x-b[k].x)+sqr(a[j].y-b[k].y))
then min:=j;
k:=k+1;
a[min].f:= true;
b[k]:=a[min] {записана очередная вершина}
until min=m; {пока ломаная не замкнется}
for j:=1 to k do {печать результата}
writeln(b[j].x,' ',b[j].y);
end.
Приведем примеры задач, при решении которых используется построение выпуклой оболочки.
Задача 1. Стена. (В англоязычном варианте задача предлагалась на студенческих командных соревнованиях по программированию в Санкт-Петербурге в 2001 г.)
Однажды жадный король приказал своему архитектору построить стену вокруг дворца. Король был настолько жадный, что не стал слушать предложения архитектора о построении стены совершенной формы. Вместо этого король приказал потратить на строительство стены определенной высоты и произвольной формы (не обязательно в виде ломаной!!!) как можно меньше кирпичей, но потребовал, чтобы стена отстояла от дворца не меньше, чем на L футов. В случае невыполнения условия или перерасхода средств архитектор может лишиться головы.
Ваша задача помочь бедному архитектору. Ваша задача написать программу, которая определит минимально возможную длину стены, которой можно окружить дворец и при этом выполнить все требования короля.
Первая строка входного файла содержит 2 числа N (3 £ N £ 1000) — количество углов в здании дворца и L (1 £ L £ 1000) минимальное расстояние на которое стена может приближаться ко дворцу. Следующие N строк описывают координаты на поверхности земли углов дворца, в порядке их обхода по часовой стрелке. Каждая строка содержит два целых числа — Xi и Yi, разделенных пробелом (-10000 £ Xi, Yi £ 10000), которые описываю координаты углов дворца в футах. Все углы дворца различны, а стороны не имеют других общих точек, кроме угловых.
Запишите в выходной файл одно число, определяющее минимальную длину дворца в футах, удовлетворяющую условию задачи. Ответ должен быть записан в виде целого числа, так как с вещественными числами король не знаком, однако округлять его следует так, чтобы целое число футов отличалось от настоящего ответа менее, чем на 8 дюймов (в 1 футе 12 дюймов).
|
|
|
| Пример входного файла | Выходной файл |
| 9 100 200 400 300 400 300 300 400 300 400 400 500 400 500 200 350 200 200 200 | 1628 |
Решение. Ответом на данную задачу будет длина выпуклой оболочки, увеличенная на длину окружности с радиусом L и округленная до ближайшего целого.
Задача 2. На плоскости заданы N точек. Построить замкнутую ломаную без самопересечений и самокасаний, вершинами которой должны стать все заданные точки. (См., например, [5], аналогичная задача предлагалась на кировской областной олимпиаде 2002г.).
Решение. Следующий рисунок проиллюстрирует идею одного из возможных способов решения данной задачи:
|
|
|
