Мальчик Вася очень любит геометрию. Кроме того, ему очень нравится забивать гвозди в доску. Сегодня он изучает свою любимую металлическую пластину, которую он собирается прибить к деревянной доске.
Пластина имеет форму, ограниченную многоугольником без самопересечений и самокасаний. В первой вершине многоугольника пластина имеет маленькую петлю.
Сначала Вася кладет пластину на доску, лежащую на горизонтальном столе, и прибивает ее гвоздем к пластине через петлю в первой вершине. Вбитый гвоздь жестко закрепляет положение первой вершины, однако позволяет пластине вращаться вокруг нее.
Теперь Вася хочет забить в доску еще один гвоздь, который бы ограничил вращение пластины, но он еще не решил куда. Он наметил \(m\) возможных позиций, куда он хотел бы забить гвоздь, и для каждой из них хочет узнать, на какой угол он сможет поворачивать свою пластину, если забьет в доску гвоздь в этой точке. При этом как только пластина касается гвоздя, дальше ее поворачивать нельзя.
В первой строке входного файла задано число \(n\) (\(3 \le n \le 2\,000\)) - количество вершин многоугольника. В следующих \(n\) строках заданы координаты вершин многоугольника в порядке обхода.
В следующей строке задано число \(m\) (\(1 \le m \le 2\,000\)) - количество точек, которые Вася рассматривает как возможные положения второго гвоздя. В следующих \(m\) строках заданы координаты этих точек. Все эти точки находятся снаружи от исходного положения пластины.
Все координаты во входном файле целые и не превосходят \(10^6\) по модулю.
Выходной файл должен содержать \(m\) строк.
В \(i\)-й строке выведите два вещественных числа \(\alpha_i\) и \(\beta_i\), где \(\alpha_i\) - максимальный угол в градусах, на который можно повернуть пластину по часовой стрелке, если Вася забьет гвоздь в \(i\)-ю точку, а \(\beta_i\) - максимальный угол в градусах ,на который в этом случае можно повернуть пластину против часовой стрелки.
Если гвоздь не мешает пластине поворачиваться, выведите \(\alpha_i = \beta_i = 360\).
Ответ считается верным, если его абсолютная или относительная погрешность относительно правильного не превосходит \(10^{-6}\).
На рисунке выше изображен тест из примера. Прямоугольник показывает начальное положение пластины. Точками показаны позиции, в которые Вася планирует забить гвоздь.
Гвоздь, забитый в первую точку, не мешает пластине поворачиваться.
Гвоздь, забитый во вторую точку, позволяет повернуть пластину на \(45^\circ\) по часовой стрелке или на \(225^\circ\) против часовой стрелки.
4 0 0 -3 -3 0 -6 3 -3 3 -8 0 -2 0 2 -1
360.000000000000 360.000000000000 45.000000000000 225.000000000000 251.565051177078 18.434948822922
Организаторы Всероссийской командной олимпиады школьников по программированию всегда ответственно относятся ко всем этапам проведения соревнования. Недавно организаторам были доставлены футболки для участников олимпиады. Они были сложены в ящик, который является кубом со стороной в один метр. Ящик был поставлен в углу комнаты прямоугольной формы размером \(m \times n\) метров. Чтобы никто случайно не забрал ящик, на его верхней грани красной краской написали слово <<ВКОШП>>.
Сегодня организаторам вдруг понадобилось переставить этот ящик в противоположный угол комнаты. Но, к сожалению, ящик оказался настолько тяжелым, что никто не мог сдвинуть его с места. Выяснилось, что все, что можно сделать с ящиком - перекатить его через ребро нижней грани. Соответствующее ребро при этом остается на том же месте, а нижней становится другая смежная с этим ребром грань.
Перед организаторами олимпиады встала следующая задача. Им необходимо перекатить ящик из угла комнаты, в котором он стоит, в противоположный угол. При этом даже перекатывать ящик очень тяжело, поэтому организаторы решили минимизировать количество перекатываний ящика.
Но когда они уже собрались начать транспортировку, обнаружилась еще одна проблема. Красная надпись <<ВКОШП>> каждый раз, касаясь пола, оставляет на нем следы. Поэтому среди всех вариантов транспортировки, минимизирующих количество перекатываний, организаторы решили выбрать тот, при котором надпись <<ВКОШП>> окажется на нижней грани куба минимальное число раз.
Помогите организаторам - посчитайте, сколько раз надпись <<ВКОШП>> коснется пола при оптимальном перекатывании куба с футболками.
В первой строке задано два числа \(n\) и \(m\) (\(1 \le n, m \le 10^9\)) - размеры комнаты в метрах.
Выведите одно число - сколько раз надпись <<ВКОШП>> окажется на нижней грани при оптимальном перемещении ящика.
В первом примере необходимо одно перекатывание, надпись, которая исходно была на верхней грани, окажется на боковой грани, но пола не коснется.
Во втором примере необходимо четыре перекатывания. В любом случае хотя бы один раз надпись <<ВКОШП>> коснется пола. Один из способов сделать перекатывания так, чтобы это произошло один раз, следующий. Сначала два раза перекатим куб в одном направлении (он окажется в соседнем углу комнаты). Сейчас надпись <<ВКОШП>> находится на нижней грани и касается пола. Затем перекатим куб еще два раза в перпендикулярном направлении. Теперь куб находится в требуемом положении.
1 2
0
3 3
1
В свете недавних новостей о прослушке каналов связи, два непримиримых интернет-гиганта Урагании «Laim.UR» и «Xenda» решили подписать соглашение об установлении защищенного канала связи между дата-центрами друг друга. В Урагании \(n\) городов, но, к сожалению, ни в одном городе нет дата-центров обоих гигантов. Поэтому для формирования защищенного канала придется прокладывать междугородние линии связи.
Специалисты компаний определили \(m\) пар городов, которые можно соединить, проложив сегмент канала связи, и оценили стоимость создания такого сегмента для каждой из этих пар.
Результирующий канал может состоять из нескольких сегментов. Он должен начинаться в одном из городов, где находится дата-центр первой компании, может проходить через промежуточные города и должен заканчиваться в городе, где находится дата-центр второй компании.
Теперь необходимо определить минимальную стоимость защищенного канала, соединяющего два дата-центра компаний.
В первой строке находятся целые числа \(n\) и \(m\) (\(2 \le n \le 5\,000\), \(1 \le m \le 10^5\)) - количество городов и количество пар городов, которые можно соединить сегментом канала связи.
Во второй строке находятся \(n\) целых чисел \(a_i\) (\(0 \le a_i \le 2\)). Если \(a_i = 0\), то в \(i\)-м городе нет дата-центра ни одного из гигантов. Если \(a_i = 1\), то в \(i\)-м городе есть дата-центр «Laim.UR», а если \(a_i = 2\), то в \(i\)-м городе находится дата-центр «Xenda». Гарантируется, что среди этих чисел есть как минимум одна единица и одна двойка.
В каждой из следующих \(m\) строк находится по три целых числа - \(s_i\), \(t_i\) и \(c_i\), которые означают, что города \(s_i\) и \(t_i\) (\(1 \le s_i, t_i \le n\), \(s_i \ne t_i\)) можно соединить сегментом канала связи стоимостью \(c_i\) (\(1 \le c_i \le 10^5\)). Каждую пару городов можно соединить не более чем одним сегментом канала.
Если соединить защищенным каналом связи два дата-центра разных интернет-гигантов возможно, то выведите в выходной файл три числа: \(x\), \(y\) и \(d\), означающие, что между городами \(x\) и \(y\) возможно провести канал связи суммарной стоимостью \(d\). В городе \(x\) должен находиться дата-центр «Laim.UR», в городе \(y\) - дата-центр «Xenda». Если существует несколько оптимальных ответов, выведите любой. Если провести искомый канал невозможно, выведите \(-1\).
В первом примере оптимально построить канал связи из двух сегментов: \(3-2\) и \(2-4\).
6 7 1 0 1 2 2 0 1 3 3 1 2 4 2 3 3 2 4 2 1 6 5 3 5 6 5 6 1
3 4 5
4 2 1 0 0 2 1 3 3 2 4 2
-1
В 2086 году в программу зимней олимпиады решено было добавить соревнования по перетягиванию каната на льду. Для проведения финала соревнования организаторы нашли \(n\) кусков каната. Для повышения зрелищности соревнования решено было сделать связать некоторые из этих кусков в один как можно более длинный канат.
Когда начались работы по связыванию, выяснилось, что на узел, связывающий два куска каната между собой, уходит по \(d\) сантиметров каната с каждого из связываемых концов. Также, оказалось, что связывать так, что получающиеся узлы находятся близко друг к другу, невозможно: расстояние между соседними узлами должно быть хотя бы \(d\) сантиметров. Например, если \(d = 10\), то после связывания кусков каната длиной 25 и 50 сантиметров, получается канат длиной 55 сантиметров, в 15 сантиметрах от одного из краев которого находится узел.
До начала соревнований остается мало времени, поэтому они обратились за помощью к вам. Помогите организаторам выяснить, канат какой максимальной длины удастся получить.
В первой строке заданы числа \(n\) (\(1 \le n \le 100\,000\)) и \(d\) (\(1 \le d \le 1000\)) - количество кусков каната и длина каната, уходящая на завязывание узла.
Во второй строке заданы \(n\) чисел \(a_i\) (\(1 \le a_i \le 1000\)) - длины имеющихся кусков каната.
Выведите единственное число- максимальную длину каната, которую можно получить.
2 10 25 50
55
5 2 4 5 6 7 8
14
Осень 2243-го года. Государства в прошлом, главным территориальным образованием является автономия. В результате терраформирования территория бывшей Евразии теперь представляет собой прямоугольник, он разбит на \(w \times h\) квадратных автономий, которые организованы в виде сетки из \(w\) автономий по ширине и \(h\) по высоте. Некоторые автономии входят в содружество Крипто, они представляют собой криптоанархистские технократические общества и не признают бюрократии. Остальные автономии входят в конфедерацию Бюрро, бюрократия в них доведена до высшего совершенства.
Для перемещения между автономиями необходим загранпаспорт. При въезде в автономию содружества Крипто предъявлять документы не нужно, но при въезде в автономию конфедерации Бюрро пограничная служба проверяет документ, заполняет специальные формы и проставляет в загранпаспорт путешественника штамп своей автономии. Один штамп занимает одну страницу паспорта, разные штампы ставятся на разные страницы.
Опытный путешественник по имени Вениамин хочет получить загранпаспорт нового образца. Чтобы это сделать досрочно, ему нужно заполнить все страницы своего старого паспорта штампами пограничных служб. На данный момент у него осталось \(n\) пустых страниц, соответственно ему нужно ровно \(n\) раз въехать в автономию Бюрро. Он хочет сделать это как можно быстрее.
Вениамин путешествует таким образом, что за один день он переезжает из автономии, в которой он находится, в автономию, имеющую с ней общую сторону. Помогите Вениамину спланировать свое путешествие так, чтобы заполнить все оставшиеся страницы загранпаспорта и при этом сделать как можно меньше переездов между автономиями. Вениамин начинает свое путешествие в родной автономии, которая принадлежит содружеству Крипто, а закончить путешествие может в любой автономии.
В первой строке входного файла содержатся три целых числа: \(w\), \(h\) и \(n\) (\(1 \le w, h \le 500\), \(1 \le n \le 1\,000\)).
В каждой из следующих \(h\) строк содержится по \(w\) символов, они задают карту Евразии. Символ «Arlaquo обозначает автономию содружества Крипто, а «T» - автономию конфедерации Бюрро. Автономия, в которой Вениамин начинает свое путешествие, обозначена символом «V».
Карта дана с севера на юг по строкам и с запада на восток по столбцам, таким образом, первый символ второй строки входного файла описывает самую северо-западную автономию.
Гарантируется, что в Евразии есть хотя бы одна автономия Бюрро.
В выходной файл выведите одну строку из символов «N», «E», «S», «W» - план путешествия Вениамина. Эти символы означают, что Вениамину следует поехать на север, восток, юг или запад, соответственно. Число перемещений в плане необходимо минимизировать, в процессе путешествия Вениамин должен ровно \(n\) раз въехать в автономию Бюрро. Если возможных оптимальных планов путешествия несколько, можно вывести любой.
5 3 6 AAATA VAATA AAAAT
EEENSNSN
3 1 2 TVT
WEW