#1244

Дремучий лес

Темы: [Элементарная геометрия]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2003, Задача H ]

Просека — эта такая прямая линия, которая проходит через лес (то есть деревья есть как с одной стороны от этой линии, так и с другой), и при этом она не проходит ни через одно из деревьев леса, а также не касается деревьев. Будем говорить, что лес является дремучим, если в нем нет ни одной просеки.

На плане леса все деревья изображаются кругами. Никакие два круга не пересекаются и не касаются друг друга. Требуется по этому плану определить, является ли лес дремучим.

Входные данные

Во входном файле содержится сначала целое число N — количество деревьев (1N200). Затем идет N троек чисел, задающих деревья. Первые два числа задают координаты центра, а третье — радиус. Все данные задаются точно, и выражаются вещественными числами, не более чем с 2 знаками после десятичной точки, по модулю не превосходящими 1000.

Выходные данные

В первой строке выходного файла должно содержаться сообщение YES, если лес является дремучим, и NO иначе. Во втором случае вторая строка выходного файла должна содержать координаты двух точек, через которые проходит просека. Все координаты нужно выводить с восемью знаками после десятичной точки, координаты не должны превышать 2000, и расстояние между выданными точками должно быть не меньше 100.

Примеры

Входные данные

3
      0.00      30.00      25.00
      0.00     -30.00      25.00
     40.00       0.00      16.00

Выходные данные

NO
     -833.3333340000      -552.7707973875
      833.3333340000       552.7707973875

Входные данные

3
      0.00      30.00      29.00
      0.00     -30.00      29.00
     40.00       0.00      19.00

Выходные данные

YES

#1378

Правила дорожного движения

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2001, Задача H ]

Город, в котором живет Петя имеет вид прямоугольника, улицы в нем образуют сетку MxN. Перед каждым перекрестком на подъезде к нему может стоять дорожный знак. Также знак может стоять после перекрестка у въезда на улицу.

В городе встречаются следующие виды дорожных знаков: знаки, установленные перед перекрестком – поворот только направо (R), поворот только налево (L), только проезд прямо (F), поворот налево запрещен (NL), поворот направо запрещен (NR), проезд прямо запрещен (NF); знаки, установленные после перекрестка – проезд запрещен (S), максимальная скорость до ближайшего перекрестка – X км/ч. (!X). В отсутствие ограничивающего знака максимальная скорость равна Y км/ч. Длина всех улиц одинакова и равна L метров. Разворачиваться на перекрестке и ехать в строго противоположном направлении не разрешается.

Петя живет в доме около перекрестка, где пересекаются x_s-я вертикальная и y_s-я горизонтальная улицы (улицы нумеруются, начиная с 1). Петин папа работает на заводе около перекрестка, где пересекаются x_d-я вертикальная и y_d-я горизонтальная улицы. Помогите Пете выяснить, какое минимальное время требуется папе, чтобы доехать на работу, если Петин папа – законопослушный водитель и соблюдает все правила дорожного движения.

Входные данные

Первая строка входного файла содержит целые числа M, N (1  M, N  20), Y (1  Y  80), L (1  L  10000), x_s, y_s, x_d и y_d (1  x_s, x_d  N, 1  y_s, y_d  M, (x_s, y_s)  (x_d, y_d)).

Следующие MN строк содержат информацию о знаках, расположенных на соответствующих перекрестках (порядок перечисления перекрестков следующий: сначала идут перекрестки, расположенные на 1-й горизонтальной улице, в возрастающем порядке номеров вертикальных улиц, затем перекрестки, расположенные на 2-й горизонтальной улице, и т.д.)

Формат информации о знаках следующий: описания знаков разделяются запятыми, сначала идет буква латинского алфавита, означающая направление, в котором уходит с перекрестка улица, на которой стоит знак, затем после двоеточия идет обозначение знака (направления обозначаются буквами N, S, E и W – см. рисунок). После последнего знака идет точка. По типу знака понятно, находится он до или после перекрестка. Ограничение скорости – целое число, 1  X  80.

Выходные данные

Выведите в выходной файл единственное число – округленное до ближайшего целого минимальное количество секунд, необходимое Петиному папе, чтобы добраться до работы (допускается ошибка в 1 секунду).

Примеры

Входные данные

3 4 60 5000 2 2 4 3
.
.
S:NL.
.
E:L.
N:S,E:S,S:S,W:!25.
S:NR.
.
.
E:!72,N:!80,W:!15.
E:!10.
.

Выходные данные

#1379

Рамка

Темы: [Условный оператор (if)]

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2002, Задача B ]

Дана рамка (края прямоугольника единичного размера). Требуется определить, можно ли замостить рамку отрезками 1 на X.

Рассмотрим прямоугольник размером X × Y, из середины которого вырезали прямоугольник размером (X – 2) × (Y – 2). Назовем такую геометрическую фигуру рамкой размера X × Y. На рисунке 1 изображена рамка размера 5 × 6.

Рисунок 1. Рамка 5 × 6

Рисунок 2. Рамка 5 × 6, замощенная плитками 3 × 1

Предположим, что у нас имеется неограниченный запас плиток размера A × 1. Рассмотрим следующую задачу: можно ли полностью замостить рамку размера X × Y такими плитками (плитки разрешается поворачивать на 90 градусов). Например, рамку 5 × 6 можно полностью замостить плитками размера 3 × 1 (один из способов показан на рисунке 2), а плитками размера 4 × 1 – нельзя.

Входные данные

Первая строка входного файла содержит два целых числа – X и Y (3 ≤ X, Y, ≤ 10⁶). Вторая строка содержит число N – количество видов плиток, которые следует проанализировать (1 ≤ N ≤ 1000). Третья строка содержит N натуральных чисел, не превышающих 10⁶. Обозначим i-ое число третьей строки входного файла за A_i.

Выходные данные

Выведите в выходной файл N строк, i-ая строка должна содержать слово yes, если можно замостить рамку размера X × Y плитками размера A_i × 1, и no в противном случае.

Примеры

Входные данные

5 6
2
3 4

Выходные данные

yes
no

#1380

Умный чертежник

Темы: [Двумерные массивы] [Стек]

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2002, Задача C ]

Линия задается набором вертикальных и горизонтальных отрезков единичной длины. Требуется изменить порядок отрезков так, чтобы линия не имела самопересечений (замена на самокасания).

Фирма "Макрохард" изобрела новое устройство с целью облегчить труд людей, кому по долгу службы приходится чертить много чертежей, а также школьников, изучающих черчение. Это устройство представляет собой крошечного робота, который умеет ползать по клетчатому листу бумаги. При этом в начале он обязательно должен быть расположен на пересечении линий сетки.

Этот робот умеет выполнять программу, которая может состоять из команд E,W,N,S — переместиться по листу в соседнюю вершину сетки вправо, влево, вперед, назад соответственно. Перемещаясь в соседний узел сетки, робот оставляет за собой ровную линию. При этом по правилам техники безопасности ему категорически запрещается проводить дважды одну и ту же линию, так как при попытке провести линию второй раз, он очень сильно пачкается в своих же собственных чернилах (они очень долго сохнут), и выходит из строя.

При этом, правда, через одну и ту же вершину сетки робот может проходить дважды. Возможно два случая (более толстой линией показано, как мы проезжаем через вершину в первый раз, более тонкой - во второй).

В первом случае мы оба раза проезжаем через вершину "прямо" (будем называть это самопересечением маршрута), а во втором случае — оба раза "поворачиваем" (это будем называть самокасанием).

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

Вам дается программа для робота. Требуется изменить ее так, чтобы узор, получающийся в конце ее работы, был таким же, но при этом при работе робота не возникало самопересечений маршрута.

Входные данные

В первой строке входного файла содержится программа для робота. Таким образом, в первой строке входного файла могут встречаться только символы E,W,N,S, а также пробельные символы, которые должны игнорироваться. Общая длина строки (включая пробельные символы) не превышает 200 символов.

Выходные данные

В выходной файл вы должны вывести одну строку с оптимизированной программой. Эта строка должна удовлетворять тем же условиям, что и входная строка.

Примеры

Входные данные

EENWSSWNN

Выходные данные

ENESWSWNN

#1381

Три из четырех

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2002, Задача D ]

Дано множество точек на плоскости, которое обладает следующим свойством: среди любых четырех из заданных точек три лежат на одной прямой.

Требуется найти ломаную, которая имеет минимальную длину и проходит через все заданные точки.

Входные данные

Первая строка входного файла содержит число N – количество точек (3 ≤ N ≤ 1000). Следующие N строк содержат координаты точек – пары целых чисел, не превышающих 10000 по абсолютной величине. Никакие две точки не совпадают.

Выходные данные

Выведите в выходной файл длину искомой ломаной с точностью не менее 10^-3.

Примеры

Входные данные

Выходные данные

3.41421356237309505