--->
39 задач
<---
Источники
Пастбища Берляндии в опасности. Волки напали на пастбище овец. Пастух решил застрелить всех волков, при этом не убив ни одной овцы. Ружье заряжено бронебойными патронами, поэтому пули пролетают насквозь. Овцы и волки представлены отрезками. Пастух находится в точке (0, 0). Траектория полета пули — луч, выходящий из точки (0, 0). Если траектория пули имеет общуюточку с отрезком, характеризующим животное, то животное умирает. Найдите наименьшее количество выстрелов, необходимое для убийства всех волков. Овцы при этом должны остаться живы.
В первой строке записаны два целых числа N и M (0 ≤ N ≤ 100000, 0 ≤ M ≤ 100000) — количество волков и овец соответственно. Далее следует N+M строк. В каждой строке записано четыре числа X1, Y1, X2, Y2 (−1000 ≤ X1, X2 ≤ 1000, 1 ≤ Y1, Y2 ≤ 1000), описывающие отрезки. Первые N отрезков описывают положение волков, следующие M строк положение овец.
Выведите наименьшее количество выстрелов, необходимое для убийства всех волков. Если невозможно убить всех волков, сохранив овец живыми, то выведите “No solution”.
1 1 5 5 6 7 3 5 8 5
No solution
2 1 1 1 2 3 -5 4 2 2 999 1000 1000 999
1
Товарищ Иванов — очень богатый любитель гаджетов. Недавно он понял, что не может купить всех гаджетов, которые он хочет потому что их никто не производит. Поэтому он решил построить свою собственную Фабрику Гаджетов.
Фабрика Гаджетов будет построена на Сколковском шоссе. На этом шоссе сконцентрировано производство нанотехнологичной продукции, необходимой для производства гаджетов. Сколковское шоссе представляет собой прямую, а фабрики — точки на этой прямой (фабрики расположены вдоль дороги).
Для производства гаджета необходимо N нанотехнологичных деталей, M фабрик производит эти детали. Товарищ Иванов хочет минимизировать сумму квадратов расстояний до ближайших фабрик, производящих необходимые детали. Помогите ему и найдите все точки для которых эта сумма минимальна.
Первая строка входного файла содержит два натуральных числа N и M (1 ≤ n ≤ 10000; N≤ M ≤ 100000)
Следующие M строк содержат пары чисел xi и pi, xi – координата i-ой фабрики, а pi – идентификатор детали, которую производит данная фабрика (xi ≤ 100000; xi ≤ xi +1; 1 ≤ pi ≤ N).
Для каждой детали существует хотя бы одна фабрика, которая производит эту деталь.
Первая строка выходного файла должна содержать целое число K — количество точек, где может быть расположена Фабрика Гаджетов.
Следующие K строк должны содержать координаты этих точек в возрастающем порядке. Значения должны выводится с точность 10-6.
3 5 -1 3 0 1 2 3 4 2 5 2
1 2.0
2 5 1 1 2 2 3 1 4 2 5 1
4 1.5 2.5 3.5 4.5
На прямой задано \(N\) попарно различных отрезков \([a_i, b_i]\) (\(i = 1, 2, \dots, N\), \(a_i < b_i\)). Будем говорить, что отрезок номер \(i\) непосредственно содержится в отрезке номер \(j\) (\(i \ne j\)), если:
Ваша задача - для каждого из данных отрезков найти тот, в котором он непосредственно содержится, либо сообщить, что таких нет. Если данный отрезок непосредственно содержится сразу в нескольких - подходит любой из них.
Сначала вводится целое число \(N\) (\(1 \le N \le 100\,000\)). Далее идут \(N\) пар целых чисел \(a_i\), \(b_i\) (\(-10^9 \le a_i < b_i \le 10^9\)).
Выведите \(N\) чисел. Число номер \(i\) должно быть равно номеру отрезка, в котором непосредственно содержится отрезок номер \(i\), либо 0 - если такого не существует.
Если существует несколько решений, выведите любое.
Тесты состоят из четырёх групп.
4 2 3 0 4 1 6 0 5
3 4 0 0
При написании программы, проверяющей ответ участника для задачи 3204 "Отрезки на прямой возвращаются" (ссылка на задачу) (прочитайте её условие!), жюри столкнулось с трудностями, превосходящими сложность самой задачи. С мыслью "почему бы и нет" написание такой программы было решено также включить в комплект задач.
Проверяющей программе доступно три блока информации:
Ваша задача - написать программу, которая по этим данным определит, правильно ли программа абстрактного участника посчитала ответ.
Вход состоит из трёх частей. Первая часть - число \(N\) (\(1 \le N \le 100\,000\)) и следом \(N\) пар \(a_i\), \(b_i\) (\(-10^9 \le a_i \lt b_i \le 10^9\)). Далее идут \(N\) чисел, каждое из которых от 0 до \(N\), \(i\)-е равно номеру отрезка, являющегося одним из непосредственно содержащих \(i\)-й, либо нулю - по мнению абстрактного участника. Далее идут ещё \(N\) чисел в том же формате - ответ жюри на эту задачу.
Входные данные всегда корректны. Это означает, например, что ответ участника не нужно проверять на соответствие формату и что ответ жюри точно правильный.
Выведите \(N\) строк. В \(i\)-й строке должен быть вердикт для \(i\)-го отрезка. Выведите OK, если ответ абстрактного участника правильный, и WA - иначе.
Тесты состоят из четырёх групп.
4 2 3 0 4 1 6 0 5 2 2 1 0 3 4 0 0
OK WA WA OK
На прямой задано некоторое множество отрезков с целочисленными координатами концов [\(L_i\), \(R_i\)]. Выберите среди данного множества подмножество отрезков, целиком покрывающее отрезок [0, \(M\)], (\(M\) — натуральное число), содержащее наименьшее число отрезков.
В первой строке указана константа \(M\) (\(1 \leq M \leq 5000\)). В каждой последующей строке записана пара чисел \(L_i\) и \(R_i\) (\(|L_i|, |R_i| \leq 50000\)), задающая координаты левого и правого концов отрезков. Список завершается парой нулей. Общее число отрезков не превышает 100 000.
В первой строке выходного файла выведите минимальное число отрезков, необходимое для покрытия отрезка [0; \(M\)]. Далее выведите список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входe. Завершающие два нуля выводить не нужно. Если покрытие отрезка [0, \(M\)] исходным множеством отрезков [\(L_i\), \(R_i\)] невозможно, то следует вывести единственную фразу “No solution”.
1 -1 0 -5 -3 2 5 0 0
No solution
1 -1 0 0 1 0 0
1 0 1