Геометрические задачи на олимпиадах по информатике

Таким образом, при решении данной задачи в случае изначально целочисленных координат мы полностью можем избежать применения вещественной арифметики, а, следовательно, избавиться от потери точности вычислений. В противном случае, в решение могут быть включены “лишние” точки, близкие к границе выпуклой оболочки или не учтены некоторые из “нужных” точек. Сложность данного алгоритма составит O(kN),

где k — количество точек в выпуклой оболочке, в худшем случае равное N. Существуют алгоритмы решения этой задачи, основанные на предварительной сортировке точек исходного множества, например, по значению угла в полярной системе координат с центром в одной из точек выпуклой оболочки, с вычислительной сложностью O(NlogN) (алгоритм Грехема). То есть наиболее трудоемкой задачей оказывается именно сортировка исходных точек.

Приведем программу решения данной задачи алгоритмом Джарвиса:

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 дюймов).

Решение. Ответом на данную задачу будет длина выпуклой оболочки, увеличенная на длину окружности с радиусом 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. Размерами селений следует пренебречь.

 Скачать реферат