всесиб 6

/*Задача 6. ПАДЪЁМ
Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Программирование — вторая
грамотность
академик Андрей Петрович Ершов
Вадима, как известного блогера-программиста, пригласили прочитать лекцию школьникам о том, как важно уметь программировать. Лекция назначена на первый урок, в зале
собрали всех учеников старших классов. К сожалению, не все школьники знают, кто такой
Вадим, и не все еще полюбили программрование. Они решили в это время поспать. Вадим
хочет, чтобы его выступление послушало как можно больше учеников. Нужно разбудить
школьников. Для этого он решил крикнуть слово «ПАДЪЁМ» достаточно громко, чтобы
школьники его услышали.
Зал можно представить на плане в виде прямоугольника размером 𝑊 на 𝐻, а школьников и Вадима — в виде точек внутри него. Школьник может находиться в двух состояниях:
спит или слушает. Спящий школьник просыпается, если слышит звук громкостью не менее
𝑃. Слушающий ученик, услышав крик Вадима громкости не менее 𝑃, начинает смеяться с
громкостью 𝐿, чем также может разбудить соседних учеников. При этом школьники достаточно умны, поэтому ученик может засмеяться только услышав крик Вадима, но не смех
другого школьника. Громкость звука линейно убывает на 𝐾 единиц за каждую единицу расстояния. Если на школьника действует несколько звуков, то их громкость не складывается.
Помогите Вадиму крикнуть с наименьшей громкостью, чтобы при этом разбудить всю
аудиторию и привлечь к себе внимание.
Формат входных данных
В первой строке входного файла заданы числа 𝑊, 𝐻, 𝑁 и 𝐾, 𝑃 и 𝐿
— размеры зала, количество школьников, коэффициент, с которым уменьшается громкость, минимальная громкость для пробуждения и громкость смеха
(1 6 𝑊, 𝐻 6 106
, 1 6 𝑁 6 2 · 105
, 1 6 𝐾 6 5, 0 6 𝑃, 𝐿 6 107
).
Во второй строке заданы 𝑥0, 𝑦0 — координаты Вадима (0 6 𝑥0 6 𝑊, 0 6 𝑦0 6 𝐻).
В следующих 𝑁 строках записано по три числа: 𝑥𝑖
, 𝑦𝑖
, 𝑠𝑖 — координаты очередного школьника и его состояние (0 6 𝑥𝑖 6 𝑊, 0 6 𝑦𝑖 6 𝐻, 𝑠𝑖 ∈ {0, 1}, 𝑠𝑖 = 0 означает, что школьник
спит, 𝑠𝑖 = 1 — слушает). Все координаты целочисленные.
Гарантируется, что никакие два ученика, а также Вадим и какой-то школьник не могут
находиться в одной точке.
Формат выходных данных
В выходной файл необходимо вывести одно число — минимальную требуемую громкость.
Ответ будет считаться верным, если его относительная или абсолютная погрешность по сравнению с правильным не превышает 10−9
.
Система оценки
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подСтраница 12 из 14
Всесибирская открытая олимпиада школьников по информатике
Отборочный очный этап, 9-11 классы, 27 ноября 2022 г.
задачи и необходимых подзадач успешно пройдены. Баллы в последней группе начисляются
за каждый пройденный тест.
Подзадача Баллы Ограничения Необходимые подзадачи
1 0 Тесты из условия
2 20 1 6 𝑁 6 2 · 104
; 1 6 𝐿, 𝑃 6 107 1
3 5 1 6 𝑁 6 2 · 105
; 1 6 𝐿, 𝑃 6 107
; все 𝑠𝑖 = 0 1
4 20 1 6 𝑁 6 2 · 105
; 1 6 𝐿, 𝑃 6 10 1
5 55 1 6 𝑁 6 2 · 105
; 1 6 𝐿, 𝑃 6 107 1, 2, 3, 4
Примеры
input.txt output.txt
8 1 3 1 1 3
6 0
5 1 0
4 1 1
3 0 0
3.23606797749978980505
1 1 1 1 1 1
0 0
1 1 1
0.00000000000000000000
1 1 1 1 1 1
0 0
1 1 0
2.41421356237309492343
4 3 6 4 1 8
2 1
3 3 0
0 0 0
3 0 0
1 0 0
2 0 1
3 1 0
9.94427190999915922021
Замечание
Первый тест представлен на рисунке.
Чёрная точка (6, 0) — позиция Вадима, красные точки — позиции спящих школьников,
зеленая точка (4, 1) — позиция единственного бодрствующего школьника.
В данном случае Вадиму достаточно крикнуть с громкостью 1 + √
5, заставив смеяться
бодрствующего школьника, который в свою очередь своим смехом разбудит обоих спящих
товарищей.
Страница 13 из*/