Страница: << 1 2 Отображать по:

#112334

Коллайдер 2.0

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

Коллайдер — это установка для изучения столкновений элементарных частиц. При его работе частицы разгоняются до большой скорости. Специальный детектор позволяет фиксировать траектории частиц в виде прямых на горизонтальной плоскости.

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

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

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

• появление новой траектории частицы,

• получение фотоснимка камерой, ориентированной по заданной направляющей прямой,

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

Формат входного файла

В первой строке входного файла задано одно целое число n (1 <= \(n\) <= 200 000) — общее количество событий. В следующих \(n\) строках заданы описания событий.

Описание каждого события состоит из пяти элементов. Первый элемент является символом «+», если это событие является появлением новой траектории, или символом «?», если это событие является получением фотоснимка. Последующие четыре элемента — целые числа \(x_1\), \(y_1\), \(x_2\), \(y_2\) (−10 000 <= \(x_1\), \(y_1\), \(x_2\), \(y_2\) <= 10 000) — координаты двух несовпадающих точек. Для событий первого типа указанные точки лежат на траектории частицы. Все траектории различны. Для событий второго типа указанные точки лежат на направляющей прямой камеры.

Формат выходного файла

Пусть \(q\) — количество полученных фотоснимков. Выходной файл должен содержать \(q\) вещественных чисел — минимальные возможные площади фотоснимков, перечисленные в порядке их получения камерой.Тест будет успешно пройден, если для каждой из \(q\) выведенных площадей выполняется условие |a - b| / (max(1, b)) <= 10^-4, где \(a\) — площадь, выведенная участником, \(b\) — площадь, полученная решением жюри.

Пояснения к примеру

Далее приведены рисунки для первого и второго примеров соответственно.

Система оценивания

Для проверки решений этой задачи используются 50 тестов. Тесты оцениваются независимо. Каждый тест оценивается в 2 балла. Значения \(n\) и \(q\), а также некоторые характеристики тестов приведены в таблице.

Тест	n	q	Примечание
1.	10	1	Направляющие прямые параллельны осям координат
2.	20	10	Направляющие прямые параллельны осям координат
3.	745	365	Направляющие прямые параллельны осям координат
4.	1997	10	Направляющие прямые параллельны осям координат
5.	2000	1000	Направляющие прямые параллельны осям координат
6.	100001	1	Направляющие прямые параллельны осям координат
7.	100002	1	Направляющие прямые параллельны осям координат
8.	200000	1	Направляющие прямые параллельны осям координат
9.	200000	100000	Направляющие прямые параллельны осям координат
10.	200000	130000	Направляющие прямые параллельны осям координат
11.	1000	10
12.	500	250
13.	10100	10000
14.	700	100
15.	800	71
16.	2001	1000
17.	5003	2000
18.	7005	4000
19.	8007	1000
20.	9009	4500
21.	90100	90001
22.	5000	101
23.	6000	98
24.	5432	2345
25.	9508	4079
26.	156002	151001	Все фотоснимки выполняются после появления всех частиц
27.	157004	152001	Все фотоснимки выполняются после появления всех частиц
28.	197062	190001	Все фотоснимки выполняются после появления всех частиц
29.	148008	141001	Все фотоснимки выполняются после появления всех частиц
30.	169010	163501	Все фотоснимки выполняются после появления всех частиц
31.	165011	159001	Все фотоснимки выполняются после появления всех частиц
32.	185001	179102	Все фотоснимки выполняются после появления всех частиц
33.	176001	168098	Все фотоснимки выполняются после появления всех частиц
34.	155433	147234	Все фотоснимки выполняются после появления всех частиц
35.	159608	152179	Все фотоснимки выполняются после появления всех частиц
36.	165011	159001
37.	185001	179102
38.	176001	174000
39.	155433	153556
40.	159608	157701
41.	200000	1
42.	110000	10
43.	120000	50
44.	199999	70
45.	188888	100
46.	200000	100000
47.	199999	195000
48.	199999	100000
49.	178689	98276
50.	199998	88888

Примеры

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

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

2.0
3.000

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

7
? 11 4 -7 8
+ -2 -2 1 1
? 0 0 0 1
+ 0 1 1 0
+ 0 2 2 0
? 0 0 0 1
? 0 0 1 1

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

#112335

Автомат с игрушками

Темы: [Обход в глубину]

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

В развлекательном центре \(Е\)-города был установлен игровой автомат нового поколения. В автомат можно бросить монету и следить за её продвижением сверху вниз по разветвляющемуся лабиринту из трубок. В лабиринте есть n узлов, которые пронумерованы числами от 1 до \(n\). При бросании монета попадает в первый узел. Каждый узел лабиринта, кроме первого, имеет одну входящую сверху трубку, по которой монета может в него попасть. Из каждого узла выходит не более двух трубок, идущих вниз, одна из которых ведет налево, а другая — направо. Каждая трубка имеет некоторую ширину. Монета проваливается в более широкую трубку, а в случае равенства ширины трубок — в левую.

После прохождения монеты по трубке ширина этой трубки уменьшается на 1. Монета не может пройти по трубке ширины 0. Если монета достигла узла, из которого она не может дальше двигаться вниз, автомат останавливается и ждёт, когда в него бросят следующую монету

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

Панкрату понравилась игрушка, которая находится в узле с номером \(v\).

Требуется написать программу, которая определяет, сколько монет должен бросить в автомат Панкрат, чтобы получить игрушку из узла \(v\).

Формат входного файла

В первой строке входного файла задано число \(n\) — количество узлов в лабиринте. В последующих n строках заданы описания всех узлов, в \(k\)-й из этих строк описан узел с номером \(k\).

Описание k-го узла состоит из четырех целых чисел: \(a_k\), \(u_k\), \(b_k\), \(w_k\). Если из \(k\)-го узла выходит левая трубка, то \(a_k\) — номер узла, в который она ведет (\(k\) < \(a_k\) <= \(n\)), а \(u_k\) — её ширина. Если левой трубки нет, то \(a_k\) = \(u_k\) = 0. Если из \(k\)-го узла выходит правая трубка, то \(b_k\) — номер узла, в который она ведет (\(k\) < \(b_k\) <= \(n\)), а \(w_k\) — её ширина. Если правой трубки нет, то \(b_k\) = \(w_k\) = 0.

В последней строке задано целое число \(v\) (1 <= \(v\) <= \(n\)) — номер узла, в котором находится игрушка, понравившаяся Панкрату.

Гарантируется, что во все узлы, кроме первого, входит ровно одна трубка

Формат выходного файла

Выходной файл должен содержать одно число — количество монет, которое необходимо бросить в автомат Панкрату, чтобы получить игрушку, которая находится в узле \(v\). Если получить выбранную игрушку невозможно, выведите число −1.

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

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

Подзадача 1

1 <= \(n\) <= 100

1 <= \(u_k\); \(w_k\) <= 300

Подзадача оценивается в 50 баллов.

Подзадача 2

1 <= \(n\) <= \(10^5\)

1 <= \(u_k\); \(w_k\) <= \(10^9\)

Подзадача оценивается в 50 баллов.

Пояснения к примеру

В первом примере первая монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 1, 3 и 4:

Вторая монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 2 и 6:

Третья монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 5 и 7:

Примеры

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

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

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

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

-1

Страница: << 1 2 Отображать по:

Выбрано

Отменить

Добавить в контест