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

((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 строк описывают координаты на поверхности земли углов дворца, в порядке их обхода по часовой стрелке. Каждая строка содержит два целых числа — X_i и Y_i , разделенных пробелом (-10000 £X_i , Y_i £ 10000), которые описываю координаты углов дворца в футах. Все углы дворца различны, а стороны не имеют других общих точек, кроме угловых.

Запишите в выходной файл одно число, определяющее минимальную длину дворца в футах, удовлетворяющую условию задачи. Ответ должен быть записан в виде целого числа, так как с вещественными числами король не знаком, однако округлять его следует так, чтобы целое число футов отличалось от настоящего ответа менее, чем на 8 дюймов (в 1 футе 12 дюймов).

Пример входного файла	Выходной файл
9 100 200 400 300 400 300 300 400 300 400 400 500 400 « 1 2 3 4 5 6 » К-во Просмотров: 218 Бесплатно скачать Реферат: Геометрические задачи на олимпиадах по информатике >>> Скачать <<< Меню Поиск