Во Флатландии n городов, расположенных в различных точках плоскости. Известно, что никакие три города не лежат на одной прямой.
Правительство решило построить в стране сеть сверхскоростных шоссе. Сеть шоссе должна быть такой, чтобы из любого города можно было проехать в любой другой по построенным шоссе. А в целях экономии средств было решено, что путь, соединяющий любые два города, должен быть единственным. Каждое шоссе представляет собой отрезок, соединяющий некоторую пару городов.
Завод, выполняющий этот госзаказ, подготовил проект сети шоссе. Проект представляет собой описание n - 1 шоссе. Каждое шоссе задается городами, которые оно соединяет. В целях секретности вместо названий городов в проекте были использованы коды – числа от 1 до n.
Однако когда дело дошло до реализации проекта, выяснилось, что документ, в котором было указано соответствие номеров городам, утерян. Поскольку проект приурочен к пятисотлетию культурной столицы Флатландии, переделывать проект полностью оказалось невозможно. Поэтому было решено установить некоторое новое соответствие номеров городам.
При попытке это сделать разработчики проекта столкнулись со следующей проблемой. В соответствии с техническими нормами строительства, недопустимо, чтобы шоссе пересекались вне городов. Поэтому не любое сопоставление номеров городам допустимо. После пары бессонных ночей главный инженер завода решил поручить спасение проекта вам.
Ваша задача – таким образом сопоставить числам от 1 до n города, чтобы после реализации проекта шоссе не пересекались вне городов, которые они соединяют.
В первой строке вводится целое число n – количество городов во Флатландии ( 2
n1500).
Далее следует n описаний городов. Описание каждого города состоит из двух строк. Первая строка содержит название города – строку, состоящую из символов с ASCII-кодами от 33 до 127. Названия различных городов не совпадают. Длина названия города не превышает 60 символов. Вторая строка описания города содержит два целых числа x и y – координаты города. Координаты не превышают 104 по абсолютной величине.
Далее следуют n - 1 строк, которые описывают проект строительства сети шоссе в его текущем состоянии. Каждая строка содержит по два целых числа – номера городов, соединенных шоссе в проекте. Никакое шоссе в проекте не соединяет город сам с собой, никакие два города не соединены более, чем одним шоссе.
Выведите n строк, i-я из этих строк должна содержать название города, который следует сопоставить числу i в проекте. Если решений несколько, выведите любое.
Если решения не существует, выведите строку «No solution».
7 Moscow 2 2 St-Petersburg 0 4 Kirov 6 3 Saratov 5 0 Rybinsk 1 1 Petrozavodsk 2 6 Barnaul 10 -1 1 2 2 4 3 5 4 3 4 7 3 6
St-Petersburg Rybinsk Kirov Saratov Moscow Petrozavodsk Barnaul
Одной из первоочередных задач, стоящих перед министерством обороны Флатландии, является модернизация вооружения. В связи с этим было решено построить новый испытательный полигон.
По форме полигон представляет собой выпуклый многоугольник. Для демонстрации военных испытаний на полигоне различным чиновникам, неподалеку от него решено было построить наблюдательный центр. В результате длительных исследований было установлено, что основной характеристикой местоположения наблюдательного центра является степень этого центра относительно полигона.
Степень точки A относительно многоугольника вычисляется по следующему правилу. Рассмотрим все лучи с вершиной в точке A, имеющие общие точки с многоугольником. Для каждого такого луча найдем минимальное и максимальное расстояние вдоль него от точки A до некоторой точки многоугольника: dmin и dmax. Степенью точки относительно данного многоугольника назовем минимум величины dmin×dmax по всем таким лучам.
Военные не справляются с задачей вычисления степени наблюдательного центра относительно полигона и решили подключить к этой задаче вас. Помогите им!
Будем считать, что наблюдательный центр находится в точке (0, 0). На вход программы поступает описание полигона.
В первой строке вводится число n – количество вершин полигона ( 3n100). Следующие n строк содержат по два вещественных числа – координаты вершин полигона в порядке обхода их против часовой стрелки. Координаты не превышают 1000 по абсолютной величине. Гарантируется, что наблюдательный центр находится вне полигона, полигон представляет собой выпуклый невырожденный многоугольник, никакие три его последовательных вершины не лежат на одной прямой. Никакая сторона многоугольника не лежит на луче с центром в начале координат.
Выведите одно число – степень наблюдательного центра относительно полигона. Ответ должен отличаться от правильного не более чем на 10-4.
3 1.0 2.0 3.0 2.0 0.5 3.25
7.0000000000