Геометрические задачи на олимпиадах по информатике (стр. 2 из 3)
Приведем программу решения данной задачи алгоритмом Джарвиса:
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 100200 400300 400300 300400 300400 400500 400500 200350 200200 200 | 1628 |
Решение. Ответом на данную задачу будет длина выпуклой оболочки, увеличенная на длину окружности с радиусом L и округленная до ближайшего целого.
Задача 2. На плоскости заданы N точек. Построить замкнутую ломаную без самопересечений и самокасаний, вершинами которой должны стать все заданные точки. (См., например, [5], аналогичная задача предлагалась на кировской областной олимпиаде 2002г.).
Решение. Следующий рисунок проиллюстрирует идею одного из возможных способов решения данной задачи:
2. Численное решение геометрических задач
В ряде случаев при решении геометрических задач формулы из вычислительной геометрии могут оказаться слишком громоздкими и приводят к решению нелинейных уравнений. Тогда на помощь могут прийти численные (приближенные) методы, позволяющие решить задачу за требуемое время и с нужной точностью. Такой подход был продемонстрирован в [6] при рассмотрении задачи “Фонтан” (ее не следует путать с задачей 6, приведенной ниже).
Из численных методов наиболее часто употребимым является метод дихотомии (деления пополам). Рассмотрим его на примере задачи XII Всероссийской олимпиады по информатике.
Задача 3. Раздел царства.
Царство царя Гороха представляет собой выпуклый N-угольник, внутри которого расположены K селений. Царь решил завещать двум своим сыновьям по полцарства, одинаковые по площади и с равным количеством селений. Для этого он требует разделить царство одной прямолинейной границей.
Напишите программу, строящую границу согласно царской воле. Если граница проходит через селение, то оно может быть либо отнесено к одному из полуцарств, либо разделено на два селения, которые будут отнесены к разным полуцарствам (при нечетном K граница, естественно, должна разделить какое-то из селений).
Первая строка входного файла содержит количество вершин многоугольника N (3 N 50). В следующих N строках заданы координаты вершин многоугольника, перечисленные в порядке обхода контура по часовой стрелке. В (N+2)-ой строке указано количество селений K (0 K 100), а в последующих K строках заданы координаты селений. Все координаты — целые числа, не превосходящие по модулю 106. Размерами селений следует пренебречь.
В выходной файл нужно вывести координаты любых двух различных точек, через которые следует провести границу. Координаты должны быть выведены с 6 знаками после десятичной точки.
| Пример входного файла | Пример выходного файла |
| 49 1020 4040 4051 10221 3040 20 | 30.000000 35.00000030.000000 15.000000 |
Решение. Выберем произвольную точку на границе царства. Для поиска прямой, проходящей через эту точку и делящей царство на две равные пока только по площади части, зафиксируем две другие точки границы, так, что прямая проведенная через выбранную и первую из фиксированных точек делит царство на две неравные части, причем левая (или нижняя для горизонтальной прямой) часть меньше правой (верхней). Прямая же, проходящая через выбранную точку и вторую из фиксированных, делит царство в обратном соотношении. Тогда искомая точка находится между двумя фиксированными и ее можно искать методом деления пополам. Теперь следует подсчитать количество селений в каждой из уже равных по площади частей. Если оно различно, то на границе нужно выбрать еще одну точку, при делении царства с помощью которой количество селений в половинах также будет соотноситься по-иному. Теперь можно применить метод деления пополам для правильного выбора опорной точки.
Задача 4. Рандеву. (VII Всероссийская олимпиада по информатике.)
Локаторы дальней космической связи замечают летящий в плоскости орбиты земли неизвестный астероид с координатами (x, y). Астероид летит с постоянной скоростью, векторное значение которой равно (Vx, Vy). С земли из точки с координатами (0, 0) немедленно стартует ракета с радиусом действия R (R > 0). Ракета летит по прямой с постоянной скоростью в пределах от 0 до W.
Требуется определить, может ли ракета подлететь вплотную к астероиду в пределах радиуса ее действия и найти вектор скорости ракеты, при котором время встречи ракеты с астероидом минимальное.
Результат решения задачи должен быть вычислен с погрешностью не более 0.01. Влиянием земли и всех космических объектов пренебречь. Ракета и астероид двигаются в одной плоскости.
В начале входного файла содержится число N — количество наборов исходных данных (тестов). Далее расположены N наборов исходных данных; каждый набор — шесть вещественных чисел: X, Y, Vx, Vy, W, R. Все числа в исходном файле разделяются пробелами и (или) символами перевода строки.
Для каждого набора исходных данных вывести с новой строки вектор скорости (Ux, Uy) и минимальное время до встречи, либо сообщение “Встреча невозможна”.
| Пример файла исходных данных | Пример выходного файла |
| 25.3 2.8 10.6 5.6 11.0 50.03.0 –4.0 –3.0 4.0 5.0 10.0 | Встреча невозможна3.0 -4.0 0.5 |
Решение. Для решения этой задачи прежде всего необходимо уметь определять взаимное расположение прямой, вдоль которой движется астероид, и окружности с центром на Земле и радиусом R. Если они не пересекаются, то встреча невозможна, в противном случае требуется отыскать точки их пересечения. Затем для поиска точки встречи с минимальным временем можно опять же применить дихотомию.
3. Различные задачи
Задача 5. “Куда идем мы с Пятачком?” (Кировское открытое командное первенство по программированию, 2001 г.)
Пятачок и Винни-Пух каждое утро ходят пить чай в гости к Кролику. Естественно, самым коротким путем. К сожалению, однажды Винни-Пуху пришла в голову идея вырыть ловушку для Слонопотама. Самое обидное, что они с Пятачком ее даже вырыли. Поэтому теперь каждое утро, идя в гости к Кролику, они боятся в нее провалиться.
Напишите программу, которая посчитает длину самого короткого безопасного пути от домика Винни-Пуха до домика Кролика.
Ловушка для Слонопотама представляет собой яму абсолютно круглой формы. Путь является безопасным, если он не проходит по ловушке (но может проходить по ее границе).
Во входном файле записаны сначала координаты домика Винни-Пуха XВYВ, затем — координаты домика Кролика XК YК, а затем — координаты центра и радиус ловушки XЛ YЛ RЛ. Все координаты — целые числа из диапазона от –32000 до 32000. Радиус ловушки — натуральное число, не превышающее 32000.