Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 97 задач <---
Источники --> Командные олимпиады --> ВКОШП
    1999(7 задач)
    2000(8 задач)
    2001(8 задач)
    2002(9 задач)
    2003(9 задач)
    2004(10 задач)
    2005(10 задач)
    2006(10 задач)
    2007(11 задач)
    2008(10 задач)
    2009(11 задач)
    2010(11 задач)
    2011(11 задач)
    2012(11 задач)
    2013(11 задач)
    2014(11 задач)
    2015(11 задач)
    2016(11 задач)
Страница: << 14 15 16 17 18 19 20 Отображать по:
#111828
Швабра
  
Источники: [ Командные олимпиады, ВКОШП, 2012, Задача J ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

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

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

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

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

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

Первая строка входного файла содержит два целых числа \(w\) и \(h\) - размеры моющей части швабры до повреждения (\(2 \le w, h \le 10^5\)).

Вторая строка содержит целое число \(n\) - число вершин ломаной, соединяющей соседние стороны швабры (\(2 \le n \le 10^5\)). В \(i\)-й из следующих \(n\) строк заданы два целых числа \(x_i\) и \(y_i\) (\(1 \le x_i < w\), \(1 \le y_i < h\), за исключением \(y_1 = h\), \(x_n = w\)) - координаты \(i\)-й вершины ломаной. Ломаная не имеет самопересечений и самокасаний.

Координаты введены таким образом, что стена, вдоль которой Рома провел шваброй, соответствует прямой \(y=h\).

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

В выходной файл выведите площадь невымытой части пола с абсолютной или относительной погрешностью не более \(10^{-6}\). Это значит, что если правильный ответ \(a\), а вы вывели \(p\), то ваш ответ будет засчитан как правильный, если \(\frac{|a-p|}{\max(|a|, 1)}\le 10^{-6}\).

Примеры
Входные данные
9 7
9
3 7
4 5
5 6
4 4
5 2
6 4
7 2
8 3
9 2
Выходные данные
18.0
#111975
Город Че
  
Источники: [ Командные олимпиады, ВКОШП, 2013, Задача B ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Девочке Маше из города Че нравятся два мальчика из ее школы, и она никак не может сделать выбор между ними. Чтобы принять окончательное решение, она решила назначить обоим мальчикам свидание в одно и то же время. Маша хочет выбрать два памятника на пешеходной улице, около которых мальчики будут ее ждать. При этом она хочет выбрать такие памятники, чтобы мальчики не увидели друг друга. Маша знает, что из-за тумана мальчики увидят друг друга только в том случае, если они будут на расстоянии не более \(r\) метров.

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

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

В первой строке входного файла находятся два целых числа \(n\) и \(r\) (\(2 \le n \le 300\,000\), \(1 \le r \le 10^9\)) - количество памятников и максимальное расстояние, на котором мальчики могут увидеть друг друга.

Во второй строке задано \(n\) положительных чисел \(d_1, \ldots, d_n\), где \(d_i\) - расстояние от \(i\)-го памятника до начала улицы. Все памятники находятся на разном расстоянии от начала улицы. Памятники приведены в порядке возрастания расстояния от начала улицы (\(1 \le d_1 < d_2 < \ldots < d_n \le 10^9\)).

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

Выведите одно число - число способов выбрать два памятника для организации свиданий.

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

В приведенном примере Маша может выбрать памятники под номерами 1 и 4 или памятники 2 и 4.

Примеры
Входные данные
4 4
1 3 5 8
Выходные данные
2
Страница: << 14 15 16 17 18 19 20 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест