На протяжении многих лет Вася работает программистом в одной очень большой и очень известной компании. Эта компания обеспечивает своих сотрудников всем необходимым для приятной и плодотворной работы: бесплатными обедами, транспортом от дома до места работы и многим, многим другим. И вот в один прекрасный солнечный день Вася понял, что ему очень наскучил вид из окна его офиса, и ему нужно, чтобы за окном было что-то новое и прекрасное. А что может быть лучше чудесного горного пейзажа? Придя к этой мысли, Вася попросил своего менеджера подобрать себе новый офис с красивым видом на горы.
В той местности, где располагается офис Васи, каждая гора принадлежит некоторой горной цепи. Так как Васе хочется, чтобы вид из окна его офиса был идеальным, то он попросил подобрать себе такой офис, чтобы никакие две горные цепи, видимые из окна, не пересекались. Менеджер Васи нашел прекрасный новый офис, из которого видно N горных цепей, но он никак не может определить, понравится ли Васе вид из окна этого офиса. Помогите ему!
Более формально, вид из окна офиса представляет собой набор горных цепей, пронумерованных от \(1\) до \(N\), где горная цепь с номером i представляет собой ломаную на плоскости из \(l_i\) звеньев с вершинами в точках (\(x_i\),\(j\) , \(y_i\),\(j\) ), причем для любых \(i\), \(j\) выполнено \(x_{i,j} < x_{i,j+1}\).
Кроме этого, окно в офисе имеет фиксированную ширину, поэтому все горные цепи начинаются и заканчиваются на одной вертикали, то есть существуют такие числа \(A\) и \(B\), что для любого номера \(i\) горной цепи выполнено \(x_{i,0} = A, x_{i,l_i} = B\).
Отметим, что из определения горной цепи следует, что для любого значения абсциссы \(A \le x \le B\) на ломаной с номером \(i\) существует единственная точка (\(x\), \(y_i\)(\(x\))) с этим значением абсциссы, принадлежащая этой ломаной. Будем говорить, что горная цепь \(i\) находится строго выше горной цепи \(j\) в точке \(x\), если выполнено строгое неравенство \(y_i(x) > y_j (x)\).
Естественно считать, что цепь под номером \(i\) пересекается с цепью под номером \(j\), если существуют такие два значения абсциссы \(x_1\), \(x_2\), что цепь \(i\) находится строго выше цепи \(j\) в точке \(x_1\), но при этом цепь \(j\) находится строго выше цепи \(i\) в точке \(x_2\), то есть выполнены неравенства \(y_i\)(\(x_1\)) > \(y_j\) (\(x_1\)) и \(y_j\) (\(x_2\)) > \(y_i\)(\(x_2\)). Обратите внимание на поясняющие рисунки, расположенные в примечании к задаче.
Вам необходимо определить, подойдет ли подобранный офис Васе, и, если нет, то найти любую пару пересекающихся горных цепей.
В первой строке входных данных через пробел идут два целых числа: \(A\) и \(B\) (\(−10^9 \le A < B \le 10^9\) ).
Во второй строке входных данных находится единственное число \(N\) — количество горных цепей, видимых из окна подобранного менеджером Васи офиса (\(1 \le N \le 100 000\)).
Далее следуют описания N горных цепей. В первой строке i-го описания содержится число \(l_i \ge 1\) — количество звеньев ломаной, из которых состоит соответствующая горная цепь. В следующих \(l_i\) + 1 строках описания содержатся два целых числа — координаты (\(x_{i, j} , y_{i,j}\) ) вершин ломаной (\(0 \le j \le l_i\)). Суммарное число звеньев всех ломаных не превосходит 200 000.
Гарантируется, что для каждой горной цепи вершины соответствующей ей ломаной идут во входных данных в порядке возрастания абсциссы, причем для любого \(i\) выполнено \(x_{i,0} = A, x_{i,l_i} = B\).
Если же офис подходит Васе, то есть никакие две горные цепи из входных данных не пересекаются, в единственной строке выходных данных выведите слово «Yes» (без кавычек).
Иначе выведите в первой строке слово «No» (без кавычек), а на следующей строке выведите два числа — номера двух пересекающихся горных цепей. Горные цепи нумеруются согласно их появлению во входных данных, начиная с 1.
В первом примере хотя ломаные и касаются друг друга в точке (−3, 2), но, согласно данному выше определению, они не пересекаются.
Во втором примере в точке \(x_1\) = 1 одна ломаная выше другой, а в точке \(x_2\) = 3 — наоборот, то есть горные цепи пересекаются.
Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
-3 3 2 1 -3 2 3 1 2 -3 2 0 4 3 2
Yes
0 4 2 3 0 3 1 3 3 1 4 1 1 0 2 4 2
No 1 2
Крешо купил вкуснейший сыр с перцем, но Степану перец не нравится, поэтому он хочет отрезать кусок, на котором не было бы перца. Сыр имеет форму выпуклого многоугольника, а каждая перчинка является точкой внутри него. Степан режет сыр только 1 раз. Он выбирает две вершины многоугольника, не являющиеся смежными, и режет по диагонали, соединяющей их. Затем Степан забирает ту из получившихся частей, на которой нет перца (ни внутри, ни на границе).
Рисунок соответствует первому тесту. Пунктирной линией показан разрез Степана.
Напишите программу, которая определит, может ли Степан отрезать кусок без перца. Если он может это сделать, выведите максимальную площадь куска, который может отрезать Степан.
Первая строка входного файла содержит одно целое число N — количество вершин в многоугольнике. Каждая из следующих N строк содержит два числа x i и y i — координаты i -й вершины. Следующая строка содержит одно число M — количество перчинок. Каждая из следующих M строк содержит два числа x i и y i — координаты i -й перчинки.
Вершины многоугольника заданы в порядке обхода против часовой стрелки и образуют выпуклый многоугольник. Никакие две подряд идущие стороны не параллельны.
Все перчинки расположены в различных точках и внутри многоугольника (они не расположены на стороне или снаружи многоугольника).
Выведите одно число — удвоенную максимальную площадь (это число всегда целое). Если отрезать кусок без перца невозможно, выведите 0.
Система оценки:
Во всех подзадачах координаты от - 10 9 до 10 9 .
5 0 1 3 0 4 2 2 3 0 3 3 2 1 3 1 3 2
4
В НИИ метеорологии решили изучить процесс образования водоемов на различных рельефах местности во время дождя. Ввиду сложности реальной задачи была создана двумерная модель, в которой местность имеет только два измерения — высоту и длину. В этой модели рельеф местности можно представить как N-звенную ломаную c вершинами \((x_0, y_0), ..., (x_N, y_N)\), где \(x_0 < x_1 < ... < x_N\) и \(y_i \neq y_j\), для любых \(i \neq j\). Слева в точке \(x_0\) и справа в точке \(x_N\) рельеф ограничен вертикальными горами огромной высоты.
Если бы рельеф был горизонтальным, то после дождя вся местность покрылась бы слоем воды глубины H. Но поскольку рельеф — это ломаная, то вода стекает и скапливается в углублениях, образуя водоемы.
Требуется найти максимальную глубину в образовавшихся после дождя водоемах.
В первой строке расположены натуральное число \(N (1 \le N \le 100)\) и \(H\) — действительное число, заданное с тремя цифрами после десятичной точки \((0 \le H \le 10^9)\). В последующих \(N + 1\) строках — по два целых числа \(x_i, y_i: -10000 \le x_i, y_i \le 10000 (0 \le i \le N)\).
Числа в строках разделены пробелами.
Ответ должен содержать единственное число — искомую глубину с точностью до 4-х знаков после десятичной точки.
7 7.000 -5 10 -3 4 -1 6 1 -4 4 17 5 3 9 5 12 15
15.8446
На координатной плоскости вдоль оси OX, симметрично относительно начала координат, мирно расположился крейсер «Адмирал Василий». Крейсер расположен так, что его центр находится в точке (0, 0) , нос (передняя часть) — в точке (− L , 0) , а корма (задняя часть) — в точке ( L , 0) . Отнюдь не мирные цели визита «Адмирала Василия» на координатную плоскость выдают лишь две его установки ПВО, расположенные на носу и корме крейсера то есть в точках (− L , 0) и ( L , 0) .
Хранители координатной плоскости не рады незваным гостям. С целью предотвращения потенциальной угрозы была выпущена ракета, направленная ровно в начало координат — центр крейсера. Ракета имеет длину
R
, на момент запуска нос ракеты находился в точке
(
X
,
Y
)
. Ракета расположена вдоль прямой, соединяющей нос ракеты и начало координат. Скорость полета ракеты —
V
(см.рисунок).
Как только ракета была запущена, её обнаружил крейсер и обе установки ПВО открыли огонь по ракете.
Установки ПВО работают следующим образом:
•они мгновенно поворачиваются, наводятся на нос ракеты и производят выстрел в этом направлении;
•скорость снаряда установки ПВО равна W ;
•установки ПВО продолжают стрелять до тех пор, пока ракета не будет уничтожена или пока крейсер не будет потоплен;
•первый выстрел установки ПВО производят в момент запуска ракеты, последующие выстрелы производятся с интервалом времени T , то есть между двумя выстрелами ракета пролетает расстояние V · T .
Если снаряд установки ПВО попадет в какую-то часть ракеты, то ракета будет уничтожена. При этом, если ракета достигнет носом центра крейсера, то , в свою очередь, крейсер будет потоплен. Какой минимальной скоростью W должны обладать снаряды установок ПВО, чтобы сбить ракету до того, как она уничтожит крейсер? Размерами снарядов установок ПВО, шириной крейсера и шириной ракеты можно пренебречь. Установки ПВО поворачиваются мгновенно. Первый выстрел они производят в момент запуска ракеты, а затем производят выстрелы с интервалом ровно T .
В первой строке входного файла содержится единственное число L — расстояние от центра крейсера до его концов ( 1 ≤ L ≤ 1000 ). Во второй строке находятся координаты носа ракеты на момент запуска — X , Y ( −1000 ≤ X ≤ 1000 , 1 ≤ Y ≤ 1000 ). В третьей строке описаны характеристики ракеты—ее длина R и скорость полета V ( 1 ≤ R , V ≤ 1000 ). В четвертой строке записано единственное число T — интервал времени между выстрелами установок ПВО ( 1 ≤ T ≤ 1000 ). Все числа во входном файле целые.
Выведите единственное число с абсолютной или относительной погрешностью не более 10 −6 — минимальную скорость снарядов установок ПВО, при которой ракету удастся сбить до того, как она потопит крейсер.
В первом примере ракета потопит крейсер через время 2. Поскольку интервал между выстрелами ПВО равен 3, то ракету нужно сбить первым выстрелом.
Во втором примере интервал между выстрелами равен 1. Значит, ракету можно сбить вторым выстрелом, для этого достаточно меньшей скорости снаряда по сравнению с первым примером.
2 0 6 2 3 3
9.486833
2 0 6 2 3 1
5.408327
В заповеднике живут q тигров. Чтобы следить за положением тигров на территории заповедника, используются ошейники с радиомаяком. Ошейник у каждого тигра имеет радиомаяк с уникальным сигналом. Система обнаружения настраивается на приём сигнала радиомаяка от i-го тигра последовательно для i от 1 до q.
Для приёма сигнала на территории заповедника установлено n приёмников в точках с координатами (x1, y1), ..., (xn, yn). Система обнаружения позволяет сотруднику заповедника за один запрос выбрать любые m (3 ≤ m ≤ n) приёмников. Выбранные приёмники должны являться вершинами выпуклого многоугольника. Система определяет, находится ли радиомаяк i-го тигра внутри этого многоугольника.
Сотрудник заповедника должен локализовать положение каждого тигра. Положение i-го тигра считается локализованным, если удалось определить такое множество приёмников, являющихся вершинами выпуклого многоугольника, что внутри этого многоугольника находится тигр, но нет других приёмников.
Для того, чтобы локализовать положение каждого из тигров, сотруднику разрешается сделать не более k запросов.
После того как положение i-го тигра локализовано, система автоматически переходит к приёму сигналов от следующего тигра, пока положение всех q тигров не будет локализовано.
Гарантируется, что никакие три приёмника не лежат на одной прямой, и ни один тигр не находится на прямой, проходящей через два приёмника. Гарантируется, что существует хотя бы один выпуклый многоугольник с вершинами в приёмниках, внутри которого находится тигр.
Требуется написать программу, которая взаимодействует с программой жюри и локализует положение каждого тигра.
Это интерактивная задача.
Сначала на вход подаётся информация об установленных в заповеднике приёмниках и количестве тигров.
Первая строка входных данных содержит целое число n — количество приёмников (3 ≤ n ≤ 5 000). Последующие n строк описывают координаты приёмников, j-я из этих строк содержит два целых числа xj и yj — координаты j-го приёмника ( - 109 ≤ xj, yj ≤ 109). Следующая строка содержит число целое число q — количество тигров (1 ≤ q ≤ 2000).
Для локализации положения тигров необходимо выполнять запросы к системе обнаружения, роль которой выполняет программа жюри.
Для каждого теста зафиксировано число k — максимальное количество запросов к системе обнаружения для локализации положения одного тигра. Гарантируется, что k запросов достаточно, чтобы решить задачу для соответствующих данных. Это число не сообщается программе-решению, но ограничения на него в различных подзадачах приведены в таблице системы оценивания. Если программа-решение делает более k запросов для определения местоположения одного из тигров, на этом тесте она получает в качестве результата тестирования «Неверный ответ».
Запрос к системе обнаружения начинается с символа «?», за которым следует целое число m — количество выбранных в запросе приёмников (3 ≤ m ≤ n), и m различных целых чисел pi — номера приёмников, перечисленные в порядке обхода многоугольника по или против часовой стрелки (1 ≤ pi ≤ n).
В ответ программа получает строку «Yes», если тигр находится внутри многоугольника, образованного приёмниками с номерами p1, ..., pm, и строку «No» в противном случае.
После того, как положение тигра локализовано, программа-решение должна вывести строку, начинающуюся с символа «!», за которым следует целое число m — количество выбранных приёмников (3 ≤ m ≤ n), и m различных целых чисел pi — номера приёмников, перечисленные в порядке обхода многоугольника по или против часовой стрелки (1 ≤ pi ≤ n). Эта строка означает, что внутри выпуклого многоугольника, образованного приёмниками с номерами p1, ..., pm, находится тигр и нет других приёмников.
Ответное сообщение от программы жюри отсутствует, и программа-решение должна немедленно приступать к поиску следующего тигра. Локализовав положение тигра с номером q, программа-решение должна завершить работу.
Тигры не перемещаются во время работы системы обнаружения. Координаты тигров в каждом тесте фиксированы и не меняются в процессе тестирования.
Если существует несколько правильных многоугольников, локализующих положение тигра, можно вывести любой из них.
На рисунке продемонстрирована процедура локализации положения каждого из тигров из приведенного ниже примера.
Приведённые примеры иллюстрируют взаимодействие программы-решения с программой жюри «по шагам», для чего в них добавлены дополнительные пустые строки. При реальном тестировании лишние пустые строки вводиться не будут, выводить пустые строки также не требуется.
