#112550

Интервалы

Темы: [Сканирующая прямая]

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

Поиск решения можно проводить с помощью двухмерной модели. В этой модели ось Ох расположена на уровне пола, источник света считается точкой с целочисленными координатами ( b _x , b _y ) . Трубы представляют собой окружности. Центр i -й окружности имеет целочисленные координаты ( с _x , c _y ) , радиус r _i также целый. Так как трубы сделаны из твердого материала, окружности не пересекаются. Трубы не отражают и не пропускают свет. Вы должны написать программу, которая найдет непересекающиеся интервалы на оси Ох , которые уже защищены от света благодаря имеющимся трубам.

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

Входной файл состоит из набора сразу нескольких тестов. Общее число строк в файле не превосходит 20000 . В первой строке каждого теста содержится положительное целое число N ≤ 10000 — обозначающее количество труб. Во второй строке расположены два целых числа b _x и b _y , разделенных пробелом. Каждая из следующих N строк содержит 3 целых числа через пробел с _x , c _y и r _i , причем c _y + r _i < b _y . Последний тест содержит единственную строку, содержащую N = 0 .

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

Для каждого теста выведите набор искомых интервалов по одному в строке. Интервал описывается двумя вещественными координатами. Ответ будет считаться правильным, если его относительная и абсолютная погрешности не будут превосходить $10^{-6}$. Интервалы должны быть отсортированы в порядке возрастания координаты x . В конце каждого набора интервалов выводите пустую строчку.

Примечание

$\text{[math]}$ $\text{[math]}$

Картинки иллюстрируют тест из условия.

Примеры

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

1
300 300
300 150 90
6
300 450
70 50 30
120 20 20
270 40 10
250 85 20
220 30 30
380 100 100
0

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

75.00 525.00

0.72 78.86
88.50 133.94
181.04 549.93

#112711

Большие скачки

Темы: [Сканирующая прямая] [Элементарная геометрия]

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

Трасса очень длинная, поэтому соревнования могут затягиваться не на один день и проходить не только днем, но и ночью. Организаторы глубоко задумались о том, как они будут освещать трассу, ведь освещать бесконечно длинную трассу не так уж и просто. Для этого они закупили N прожекторов, которые будут установлены в некоторых точках города. Известно что прожекторы освещают землю, образуя круги.

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

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

Первая строка входного файла содержит четыре числа x ₁ , y ₁ , x ₂ , y ₂ — координаты двух точек на прямой. Во второй — строке число N ( 1 ≤ N ≤ 100000 ) — количество прожекторов. В каждой их следующих N строк заданы 3 числа x , y и R , координаты и радиус кругов, образованных прожекторами.

Все координаты и радиусы — целые числа, не превышающие по модулю 10 ⁵ .

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

В выходной файл выведите ответ на задачу, с точностью до 10 ^- 4 .

Примечание

$\text{[math]}$ Этот рисунок соответствует второму примеру. Отмеченная жирной линией часть дороги, является освещенной.

Примеры

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

0 0 1 1
1
5 5 1

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

2.000000000000001

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

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

18.446020156281286

#112817

Вышивка жемчугом

Темы: [Сканирующая прямая] [Алгоритмы на графах]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2015, 1 тур, Задача C ]

Дано изображение дерева из $n$ вершин на прямоугольной сетке. Каждое ребро — либо вертикальный, либо горизонтальный отрезок длины $1$ Дано $q$ запросов, каждый имеет вид "сколько компонент связности образуется при вырезании данного прямоугольного фрагмента"

Со стародавних времён в поморских деревнях рукодельницы вышивали жемчугом на прямоугольных полотенцах, состоящих из одинаковых клеток. Вышивка начиналась с пришивания жемчужины к полотенцу в центре одной из клеток. Чтобы пришить новую жемчужину, рукодельница делала стежок из клетки, уже содержащей жемчужину, в соседнюю с ней по горизонтали или вертикали свободную клетку. Новая жемчужина пришивалась в центре клетки на конце стежка. Этот процесс повторялся, пока не заканчивались жемчужины.

Одно из таких праздничных полотенец находится в музее. К сожалению, некоторые части узора были утеряны, но описание полотенца сохранилось. Дирекция музея планирует восстановить один из прямоугольных фрагментов полотенца, но не ещё не решила какой именно. Затраты на восстановление фрагмента зависят от количества связных частей узора, попавших на этот фрагмент. Часть узора считается связной, если от любой её жемчужины можно по стежкам перейти к любой другой её жемчужине, не выходя за границы фрагмента. Дирекция всегда относит любые две жемчужины, между которыми можно перейти по стежкам, к одной и той же связной части узора.

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

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

Первая строка входных данных содержит два целых числа a и b — размеры полотенца в клетках по горизонтали и вертикали.

Вторая строка содержит два числа $n$ и $q$ — количество жемчужин в узоре и количество фрагментов соответственно.

Следующие ($n − 1$) строк содержат описания стежков. Каждый стежок имеет один из следующих видов:

• $h \times y$ означает, что клетки с координатами $(x, y)$ и $(x + 1, y)$ содержат жемчужины, соединённые горизонтальным стежком ($1 \le x \le a − 1; 1 \le y \le b$);

• $v \times y$ означает, что клетки с координатами $(x, y)$ и $(x, y + 1)$ содержат жемчужины, соединённые вертикальным стежком ($1 \le x \le a; 1 \le y \le b − 1$).

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

Следующие $q$ строк описывают фрагменты. Каждое описание содержит четыре целых числа $x_1$, $y_1$, $x_2$ и $y_2$ — координаты левой нижней и правой верхней клетки фрагмента ($1 \le x_1 \le x_2 \le a; 1 \le y_1 \le y_2 \le b$).

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

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

Таблица системы оценивания

Замечание

Пояснение к тесту из условия

Примеры

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

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

#113176

Песочница

Темы: [Сканирующая прямая] [Сортировка событий]

Прямоугольная детская площадка полностью замощена $N$ плитками. Все плитки прямоугольные, возможно разного размера. Плитки не перекрываются.

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

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

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

Введем систему координат так, чтобы начало координат совпадало с одним из углов площадки, а оси координат шли вдоль сторон площадки. В этом случае противоположный угол площадки окажется в точке $(X,Y)$.

Первая строка содержит два числа $X$ и $Y$ (натуральные числа, не превышающие 10000). Во второй строке заданы числа $N$ и $K (1 \le K \le N \le 2000)$. Следующие $N$ строк файла содержат по четыре целых числа $X_{i,1}, Y_{i,1}, X_{i,2}, Y_{i,2}$, задающих координаты двух противоположных углов плитки.

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

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

Система оценки

В этой задаче 16 тестов, каждый тест оценивается независимо.

Гарантируется, что решения, корректно работающие при $n \le 25$ наберут не менее 30 баллов.

Гарантируется, что решения, корректно работающие при $n \le 500$ наберут не менее 42 баллов.

Гарантируется, что решения, корректно работающие при $n \le 1500$ наберут не менее 54 баллов.

Примеры

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

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

0 1 4 4

#113557

Держава

Темы: [Сканирующая прямая] [Бинарный поиск по ответу] [Система непересекающихся множеств]

Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 2, Держава ]

В далекой стране есть N городов. Был избран новый премьер-министр. В настоящее время в этой стране нет ни одной дороги, поэтому премьер-министр решил модернизировать страну, соединив некоторые города с двусторонними автострадами в транспортные сети. Два города будут расположены в одной и той же сети, если можно добраться до одного города от другого, используя недавно построенные дороги. Каждый город будет расположен в какой-то сети. Каждая сеть состоит из одного или нескольких городов.

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

В настоящее время страна переживает экономический спад, поэтому премьер-министр решил, что из-за отсутствия бюджета они не будут строить дороги длиннее, чем D километров. Кроме того, премьер-министр радуется мелочам, поэтому он будет счастлив, если по крайней мере в одной сети будет существовать непустое подмножество городов (оно может включать все города в сети), где общая сумма жителей делится на К . Например, если K = 4 и есть сеть с городами, в которых есть 3 , 5 , 7 жителей соответственно, премьер-министр будет счастлив, потому что сумма жителей в первых двух городах равна 8 .

Помогите премьер-министру сократить расходы, определив минимальный уровень D , необходимый для того чтобы премьер-министр мог строить дороги и одновременно быть счастливым.

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

Первая строка ввода содержит целые числа N и K (1 ≤ N ≤ 50000, 1 ≤ K ≤ 30) . Каждая из следующих N строк содержит три целых числа x _i ; y _i ; k _i (0 ≤ x _i , y _i , k _i ≤ 100000000) , которые представляют координату x города, координату y и количество жителей в этом городе, соответственно. На входных данных не будет двух городов с одинаковыми координатами. Кроме того, не будет ни одного города, в котором число жителей делится на К .

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

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

Примечание

Объяснение первого примера: единственный способ удержать премьер-министра в счастливом настроение - все города должны находятся в одном округе. Минимальный D , для которого это возможно, равен 1.414 .

Объяснение второго примера: премьер-министр будет рад, если первые 5 городов находятся в одном округе. Если D = 5.657 , премьер-министр может соединить города 1, 2, 3, 5 с городом 4 . В этом случае сумма жителей в городах 1, 2, 3, 4, 5 составит 11 , что делится на 11 , Поэтому премьер-министр будет счастлив.

Примеры

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

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

1.414

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

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

5.657

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

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

2.000