Задача A. Спасти моллюска ≡

Условие

Исследователи морских глубин обнаружили новый вид донных моллюсков, обладающих сложной организацией. Ареал обитания этих существ представлен областью, изображенной на рисунке и характеризующейся десятью параметрами (буквы a − l). В зависимости от различных условий, ареал изменяется в размерах, но форма его остается неизменной. Однако, когда ареал сокращается, также резко падает и популяция моллюсков.

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

Напишите программу, которая поможет ученым определить, попадет ли дрон в ареал обитания моллюсков, если ему задать координаты выбранную точку x_k,y_k и параметры области (a − l), если считать, что центр области (обозначенный на рисунке (0, 0)) зафиксирован и его можно принять за начало координат. Границы области включены в ареал обитания.

Примечание. В ходе решения может пригодиться уравнение прямой (x − x_i) / (x_j − x_i) = (y − y_i) / (y_j − y_i), проходящей через две точки (x_i,y_i) и (x_j,y_j).

Формат входных данных

В первых десяти строках входных данных вводятся целые положительные числа – параметры области a, b, c, d, e, f, g, h, k, l.

В одиннадцатой строке вводится пара целых чисел через пробел - координаты точки установки зонда x_k, y_k.

Формат выходных данных

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

Ограничения

Параметры области a, b, c, d, e, f, g, h, k, l и координаты точки спуска зонда x_k, y_k – целые числа, для любого из этих чисел выполняются условия 0 ≤ i ≤ 10000.

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

Примеры тестов

14
7
11
8
5
5
4
11
11
3
4 4

NO

14
7
11
8
5
5
4
11
11
3
6 0

YES

Задача B. Энергетический кабель ≡

Условие

Вокруг объектов глубоководной исследовательской станции по окружности радиусом r км размещен энергетический кабель. Оценку его состояния осуществляют передвижные беспилотные аппараты, оснащенные системой компьютерного зрения. Каждый день роботы начинают движение вдоль кабеля из одной точки в противоположных направлениях с постоянными скоростями v и u км/час соответственно, делая по несколько витков каждый. Через сколько часов аппараты встретятся в n-й раз после начала движения? Радиус r достаточно велик, чтобы считать движение аппаратов на отдельном участке пути прямолинейным и равномерным.

Формат входных данных

Единственная строка содержит четыре целых числа, каждое из которых отделено от другого одним пробелом, r, v₁, v₂, n, где r – радиус окружности в км, v₁ – скорость первого аппарата, км/ч, v₂ – скорость второго аппарата, км/ч, n – количество встреч аппаратов после старта.

Формат выходных данных

Выведите единственное целое число t (округление до целого провести по правилам математики), которое показывает, через сколько часов аппараты встретятся в n-й раз после начала движения.

Ограничения

0 < r ≤ 10³

0 < v₁ ≤ 10²

0 < v₂ ≤ 10²

0 < n ≤ 10²

v₂ < v₁

Примеры тестов

10 5 4 2

14

967 99 70 64

2301

Задача C. Глубина движения по траектории ≡

Условие

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

Примечание. Медианой x_med последовательности чисел называется такое из них, что 50% значений последовательности меньше либо равно медиане, а оставшиеся 50% - больше либо равны медиане. Например, допустим, имеется отсортированный массив длины n, нумерация элементов начинается с 1. Тогда x_med = x_{((n + 1) / 2)}, в случае, если число n - нечетно. Если n - четно, то медиана равна: x_med = (x_(n / 2) + x_{(n / 2 + 1)} / 2).

Формат входных данных

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

Формат выходных данных

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

Ограничения

1 ≤ N ≤ 10⁵

0 ≤ a_i ≤ 10⁴, где a_i - элемент массива

Примеры тестов

5
3 5 1 2 4

3.00

6
3 5 1 6 2 4

3.50

Задача D. Движение батискафов ≡

Условие

К 3056 году люди смогли покорить морские глубины и организовали небольшой подводный городок, в котором появилось несколько улиц и даже общественный транспорт. Сеть дорог содержит N перекрестков, каждые два из которых соединены одной улицей. По улицам курсирует два маршрута батискафов, каждый из которых является кольцевым.

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

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

Формат входных данных

Первая строка входных данных содержит число N – количество перекрестков в подводном городке (3 ≤ N ≤ 30000). Следующие две строки содержат описание маршрутов в следующем формате: сначала идет K_i – количество перекрестков, через которые проходит маршрут (3 ≤ K_i ≤ N), затем перечислены эти перекрестки в том порядке, в котором их посещает батискаф соответствующего маршрута. Числа в строках разделены одним или несколькими пробелами.

Формат выходных данных

Выведите номера перекрестков, которые соединяет улица, по которой ходят оба батискафа, в возрастающем порядке.

Ограничения

3 ≤ N ≤ 30000

3 ≤ K_i ≤ N

Примеры тестов

6
6 1 2 3 4 5 6
6 1 5 3 6 4 2

1 2

Задача E. Размещение сенсорных узлов ≡

Условие

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

Пример 2 входных / выходных данных является тривиальным случаем и должен обрабатываться отдельно.Необходимо вывести координату последней контрольной точки.

Формат входных данных

В первой строке вводятся числа N – количество контрольных точек и K – количество сенсорных узлов. Во второй строке задаются N натуральных чисел в порядке возрастания – координаты контрольных точек на прямой линии (координаты не превосходят 10⁹)

Формат выходных данных

Выведите одно число – наибольшее возможное допустимое расстояние между сенсорными узлами.

Ограничения

2 < N < 10001

1 <  = K < N

Примеры тестов

6 3
2 5 7 11 15 20

9

7 1
1 2 3 4 5 6 7

7