Страница: << 1 2 3 4 5 >> Отображать по:
#1625
Санная трасса
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Как известно, к северу от Москвы находится много горнолыжных трасс, расположенных на холмах Клинско-Дмитровской гряды. Один из курортов в связи с финансовым кризисом решил расширить спектр услуг, предлагая трассы для катания не только на лыжах и сноубордах, но и санные трассы.

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

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

На приведенном рисунке пунктирной линией показана наилучшая трасса для \(K\) = 4. Разница высот в ней составляет 68.

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

Сначала вводятся два натуральных числа \(C\) (1 ≤ \(C\) ≤ 2 000) — количество окружностей и \(K\) (1 ≤ \(K\) ≤ 2 000) – максимальное количество окружностей, которое может пересечь трасса.

Далее идут описания окружностей, каждое из которых состоит из четырех целых чисел: \(X\), \(Y\) (–2000 ≤ \(X\) ≤ 2000, –2000 ≤ \(Y\) ≤ 2000) – координаты центра окружности, \(R\) (1 ≤ \(R\) ≤ 2000) — радиус окружности и \(A\) (–1000 ≤ \(A\) ≤ 1000) — высота местности, касающейся внутреннего края окружности.

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

Выведите одно число — максимальный перепад высот на трассе.

Пример

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

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

10 4

38 61 2 73

69 34 3 15

61 59 4 30

40 60 5 66

58 44 6 30

71 34 6 -2

47 21 6 45

41 58 8 52

41 57 11 37

48 40 33 10

68
#1752
Автобусы
  
Заданы прямоугольные рамки с вершинами в целых точках и со сторонами параллельными осям координат. Требуется найти количество точек, лежащих на всех рамках.

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

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

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

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

На первой строке входного файла находится число \(n\) (1 ≤ \(n\) ≤ \(10^4\)) – количество маршрутов. Далее следуют \(n\) строк, на каждой из которых находятся две пары целых чисел – координаты двух противоположных вершин прямоугольника, по которому проходит данный маршрут. Все координаты не превосходят \(10^8\) по абсолютной величине.

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

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

Примеры
Входные данные
1
0 0 1 1
Выходные данные
4
#1762
Старая крепость
  
Из окружности вырезано некоторое количество фрагментов. Требуется найти минимальную выпуклую оболочку (провести между оставшимися фрагментами хорды).

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

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

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

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

Во входном файле задано два натуральных числа: число фрагментов \(n\) (1 ≤ \(n\) ≤ 180) и радиус крепости \(r\) (1 ≤ \(r\) ≤ 100). Далее следует n пар целых чисел, описывающих сохранившиеся фрагменты стены: \(a_i\), \(b_i\) – углы в градусах, соответствующие началу и концу фрагмента. Углы отмеряются от направления на север из центра крепости, против часовой стрелки (0 ≤ \(a_i\), \(b_i\)< 360, \(a_i\) ≠ \(b_i\)). Каждый фрагмент от начального угла к конечному также проходится против часовой стрелки. Фрагменты не имеют общих точек.

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

Выведите минимальную возможную длину забора. Ответ должен отличаться от правильного не более, чем на \(10^{-3}\).

Примеры
Входные данные
1 100
0 90
Выходные данные
298.5009889168
#1771
Свечки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
На круглом торте расположены свечки, заданные двумя координатами. Разрезы торта заданы уравнениями прямых. Требуется определить, есть ли на каком-либо кусочке торта более одной свечки.

Мише исполнилось \(n\) лет. Праздничный торт, испеченный по этому случаю, имеет форму круга радиуса \(r\) с центром в начале координат. На торте стоят \(n\) свечек. Мишина мама разделила торт на части, сделав \(m\) прямолинейных разрезов. Каждый гость взял один из получившихся кусков.

Миша хочет узнать, не досталось ли кому-нибудь из его гостей более одной свечки. Помогите ему это выяснить.

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

Первая строка входного файла содержит целые числа \(n\), \(m\) и \(r\) (1 ≤ \(n\) ≤ 10000, 0 ≤ \(m\) ≤ 1000, 1 ≤ \(r\) ≤ 2000).

Следующие n строк содержат пары целых чисел \(x_i\), \(y_i\) – координаты точек, где расположены свечки. Гарантируется, что эти точки лежат внутри круга, размерами свечек следует пренебречь. Никакие две свечки не совпадают.

Последние \(m\) строк содержат описание разрезов – тройки целых чисел \(a_i\), \(b_i\), \(c_i\). Такая тройка соответствует разрезу, который задается уравнением \(a_i\) \(x\) + \(b_i\) \(y\) + \(c_i\) = 0. Ни один разрез не проходит через свечку. Никакие два разреза не совпадают. Числа ai, bi, ci не превышают 10000 по модулю.

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

Если одному из гостей досталось более одной свечки, выведите в выходной файл слово «YES», иначе выведите слово «NO».

Примеры
Входные данные
3 2 3
2 2
1 -1
-2 0
2 -1 0
0 1 -1
Выходные данные
NO
Входные данные
3 2 3
2 2
1 -1
-2 0
1 1 -1
0 1 -1
Выходные данные
YES
Входные данные
4 2 10
1 1
1 -1
-1 1
-1 -1
0 1 0
1 0 0
Выходные данные
NO
#1784
Про любовь...
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

Входной файл содержит 12 чисел: \(x_1\), \(y_1\), \(x_2\), \(y_2\), \(x_3\), \(y_3\), \(x_4\), \(y_4\), \(v_{1x}\), \(v_{1y}\), \(v_{2x}\), \(v_{2y}\). Координаты вершин первого отрезка: (\(x_1\), \(y_1\)) и (\(x_2\), \(y_2\)), координаты вершин второго отрезка: (\(x_3\), \(y_3\)) и (\(x_4\), \(y_4\)), скорость первого отрезка (\(v_{1x}\), \(v_{1y}\)), скорость второго отрезка (\(v_{2x}\), \(v_{2y}\)). Все числа целые и не превосходят по модулю \(10^4\). В начальный момент времени веточки не соприкасаются. Гарантируется, что веточки имеют ненулевую длину.

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

Выведите в выходной файл время до ближайшего момента, когда веточки соприкоснутся, с ошибкой не более \(10^{-4}\). Если веточки не соприкоснутся никогда, выведите число -1.

Примеры
Входные данные
0 0 -1 3
4 4 7 7
3 0
0 -1
Выходные данные
1.6
Входные данные
0 0 -1 3
4 4 7 7
1 0
0 -3
Выходные данные
-1
Страница: << 1 2 3 4 5 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест