1. Набираем команду codeby webinar. Набираем команду для организации и проведения вебинаров. Подробнее ...

    Скрыть объявление
  2. Требуются разработчики и тестеры для проекта codebyOS. Требования для участия в проекте: Знание принципов работы ОС на базе Linux; Знание Bash; Крайне желательное знание CPP, Python, Lua; Навыки системного администрирования. Подробнее ...

    Скрыть объявление
  3. Получи 30.000 рублей. Для получения денег необходимо принять участие в конкурсе авторов codeby. С условиями и призами можно ознакомиться на этой странице ...

    Внимание! Регистрация авторов на конкурс закрыта.

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

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

Тема в разделе "Свободное общение", создана пользователем 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
    Помогите решить пожалуйста, срочно нужно.
     
Загрузка...

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