11/04/2025 01:20:18

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1986. Строительство водопровода

Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

От артезианской скважины до всех домов в поселке нужно проложить водопровод. Можно сэкономить при строительстве, используя несколько больших труб, проложенных еще в доперестроечные времена. Новые трубы имеют меньший диаметр, чем старые, и их можно прокладывать по прямой линии либо между двумя домами, либо между домом и скважиной, либо между домом или скважиной и любой точкой старой трубы, либо между любыми точками двух старых труб.

Напишите программу, которая определяет минимальную длину новых труб.

Первая строка ввода содержит два целых числа: количество домов

$N$ в поселке и количество старых труб

$K$ (

$1\ ≤\ N\ ≤\ 100$ ,

$1\ ≤\ K\ ≤\ 10$ ). Далее следует строка с координатами скважины и

$N$ строк с координатами домов. Далее следует

$K$ строк с координатами концов старых труб. Все координаты являются целыми числами в диапазоне от 0 до 1000. Старые трубы не пересекаются между собой, но могут соприкасаться концами. В первой строке вывести минимальную длину новых труб с точностью

$10^{-6}$ .

Пример ввода

Пример вывода

4.236068

05/10/2013	Личное первенство Южного Урала (F)
12/07/2016	Лето 2016 - 8 (C)