Темы --> Информатика --> Алгоритмы --> Вычислительная геометрия
    Градиентный спуск(1 задач)
    Элементарная геометрия(144 задач)
    Многоугольники. Выпуклые оболочки(38 задач)
    Клеточная геометрия(8 задач)
    Квадродерево(3 задач)
---> 2 задач <---
Источники --> Командные олимпиады --> Кировские командные турниры
    2001(8 задач)
Страница: 1 Отображать по:
#1128
Куда идем мы с Пяточком?
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
На плоскости есть непроходимый круг. Необходимо найти кратчайший путь от точки до точки.

«Кто ходит в гости по утрам, тот поступает мудро…»

Пятачок и Винни-Пух каждое утро ходят пить чай в гости к Кролику. Естественно, самым коротким путем.

К сожалению, однажды Винни-Пуху пришла в голову идея вырыть ловушку для Слонопотама. Самое обидное, что они с Пятачком ее даже вырыли. Поэтому теперь каждое утро, идя в гости к Кролику, они боятся в нее провалиться.

Напишите программу, которая посчитает длину самого короткого безопасного пути от домика Винни-Пуха до домика Кролика.

Ловушка для Слонопотама представляет собой яму абсолютно круглой формы. Путь является безопасным, если он не проходит по ловушке (но может проходить по ее границе).

Входные данные

Во входном файле записаны сначала координаты домика Винни-Пуха XВ YВ, затем — координаты домика Кролика XК YК, а затем — координаты центра и радиус ловушки XЛ YЛ RЛ. Все координаты — целые числа из диапазона от –32000 до 32000. Радиус ловушки — натуральное число, не превышающее 32000.

Домики Винни-Пуха и Кролика не могут находиться внутри ловушки, но могут находиться на ее границе.

Выходные данные

Выведите в выходной файл одно число — длину самого короткого безопасного пути от домика Винни-Пуха до домика Кролика с тремя знаками после точки.

Примеры
Входные данные
0 0 10 0
5 5 1
Выходные данные
10.000
Входные данные
3 4 4 4
0 0 5
Выходные данные
1.000
#1134
РЛС
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Задана карта района, на которой присутствуют не более 5 связных фигур из клеток. Необходимо окружить все клетки забором минимальной длины (при этом группы клеток можно окружать отдельным забором).

Задачи противовоздушной обороны: ...борьба с десантом на всем маршруте пролета,

уничтожение вертолетов огневой поддержки, действующих из засады»

Радиолокационная станция (РЛС) состоит из нескольких передатчиков (не более 5). К сожалению, их нельзя ставить рядом — они друг для друга создают помехи. Каждый передатчик состоит из квадратных модулей, которые располагаются вплотную друг к другу.

Вам дана карта района, в котором расположена РЛС. Вся карта для удобства разбита на квадраты, и для каждого квадрата известно, располагается в нем какой-то из модулей одного из передатчиков РЛС или нет.

Требуется оградить забором (или несколькими заборами) минимально возможной суммарной длины все передатчики РЛС. Забор — это произвольная ломаная (ее элементы не обязаны идти по сторонам клеток). Одним забором могут быть огорожены сразу несколько передатчиков.

Входные данные

Во входном файле записаны два числа N и M, задающие размеры района, в котором расположена РЛС (1N20, 1M20). Далее идет N строк, по M чисел в каждой, задающих карту района. Каждое из этих чисел 0 или 1 — 1 означает, что в этом квадрате находится один из модулей передатчика РЛС, а 0 — что в этом квадрате ничего ценного нет.

Общее количество передатчиков РЛС не превышает 5. Каждый передатчик — это связанная группа модулей (модули называются связанными, если они располагаются в квадратах карты, у которых есть общая граница, либо связаны через какие-то другие модули).

Ограничения на число модулей нет.

Выходные данные

В выходной файл выведите одно число — минимально возможную длину забора с тремя значащими цифрами после точки.

Примеры
Входные данные
2 2
1 0
0 1
Выходные данные
6.828
Входные данные
4 5
1 0 0 0 1
0 0 0 0 0
0 0 1 0 0
1 0 0 0 1
Выходные данные
18.000
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест