1. Спонсор публикаций Marketplace codeby. Сервис, который так долго ждали. При расчетах используем биткоин. Первый товар уже в продаже: Консультация на тему ИБ от Ondrik8

    Скрыть объявление
  2. Спонсор публикаций Marketplace codeby. Сервис, который так долго ждали. При расчетах используем биткоин. Второй товар маркетплейса: Надёжная обфускация вашей программы от PingVinich

    Скрыть объявление

Задача "Острова"

Тема в разделе "Свободное общение", создана пользователем Wolf.bris, 11 апр 2009.

  1. Wolf.bris

    Wolf.bris Гость

    Репутация:
    0
    Имеется такая задача
    В океане расположен архипелаг из N островов, каждый из которых имеет форму выпуклого многоугольника. Острова не соприкасаются и не пересекаются. Эти острова необходимо соеденить между собой мостами так, чтобы от любого острова архипелага можно было добраться до любого другого. Каждый мост должен соеденять пару островов, при этом суммарная длинна мостов должна быть минимальной.
    Вход: файл input.txt, имеющий следующую структуру: в первой строке входного файла записано число N – количество островов в архипелаге. Далее идет N строк с описанием островов. В каждой строке описывается один остров, который задаётся числом вершин (первое число строки) и далее их координатами в порядке обхода по часовой стрелке (у каждой вершины первой идет абсцисса, а второй - ордината). Координаты внутри строки разделяются пробелами.
    Ограничения: число N – натуральное от 2 до 50 (включительно), для каждого острова число вершин не превосходит 20, все координаты – целые числа, не превосходящие по модулю 30000.
    Выход: файл output.txt, содержащий два числа (по одному в строке), первая строка ¬- число: количество мостов; второе строка - число: суммарная длина мостов с точностью до 0.001
    ПРИМЕР
    Входной файл input.txt содержит:
    2
    4 –2 –2 –2 2 2 2 2 –2
    3 3 –2 3 2 6 0
    Результат (файл output.txt):
    1
    1
    Помогите решить пожалуйста, срочно нужно.
     
Загрузка...
Похожие Темы - Задача Острова
  1. disub
    Ответов:
    1
    Просмотров:
    115
  2. Kazua
    Ответов:
    1
    Просмотров:
    96
  3. Rina
    Ответов:
    0
    Просмотров:
    70
  4. School_Information

    Решите Задача

    Ответов:
    2
    Просмотров:
    211
  5. KhNarg
    Ответов:
    2
    Просмотров:
    330

Поделиться этой страницей