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

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

  1. Wolf.bris

    Wolf.bris Гость

    Имеется такая задача
    В океане расположен архипелаг из 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. Янчик
    Ответов:
    0
    Просмотров:
    478
  2. TrishaRay
    Ответов:
    1
    Просмотров:
    778
  3. elzim
    Ответов:
    0
    Просмотров:
    929
  4. ShaoKahn
    Ответов:
    0
    Просмотров:
    1.117
  5. eremin-sanek
    Ответов:
    3
    Просмотров:
    1.104

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