--->
8 задач
<---
#1617
Темы:
[Элементарная геометрия]
Источники:
[
Командные олимпиады,
Московская командная олимпиада,
9-11 классы,
2009,
Лига А,
Задача B
]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
На территории будущей стройки растут три дерева. Фирма получила разрешение на строительные работы с условием, что два (любых) дерева будут сохранены. Прораб хочет построить забор треугольной формы так, чтобы внутри него оказалось ровно два дерева.
Деревья на плане изображаются кругами, которые попарно не вложены друг в друга и не пересекаются (но могут касаться).
Напишите программу, которая по введенной информации о деревьях определит, возможно ли построить такой забор, и, если да, то какое дерево окажется не огорожено.
Входные данные
Вводится информация о трех деревьях: для каждого дерева координаты центра и радиус круга, изображающего это дерево на плане. Все числа целые, не превосходящие по модулю 3000. Радиус – натуральное число.
Выходные данные
Выведите одно число – номер дерева (деревья нумеруются начиная с 1 в порядке задания их во входных данных), которое окажется не огорожено. Если забор треугольной формы, огораживающий ровно два дерева, построить невозможно, выведите число 0. Если существует несколько решений, выведите любое.
#1625
Темы:
[Обход в ширину]
[Элементарная геометрия]
Источники:
[
Командные олимпиады,
Московская командная олимпиада,
9-11 классы,
2009,
Лига А,
Задача J
]
ограничение по времени на тест
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 |
#111271
Темы:
[Элементарная геометрия]
Источники:
[
Командные олимпиады,
Московская командная олимпиада,
9-11 классы,
2012,
Лига А,
Задача F
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
6 megabytes
На Международной олимпиаде по информатике некоторые участники, конечно же, получают удовольствие именно от решения предложенных задач, но большинство — от полученных в новой стране впечатлений. Впечатления принято запечатлевать на фотоаппарат. Участник T решил подойти к процессу съёмок с научной (по его мнению) точки зрения. Он находится на круглой обзорной площадке и желает заснять сразу два интересных объекта, местоположение каждого из которых на земле мы будем описывать с помощью отрезка. T выбирает точку для съёмок внутри этой площадки так, чтобы суммарная площадь двух треугольников, образованных концами соответствующих отрезков и выбранной точкой на обзорной площадке была как можно больше.
Помогите T с выбором такой точки. Возможность заснять сразу два объекта при этом анализировать не нужно, мы лишь действуем в рамках модели, сформулированной T. Если объекты загораживают друг друга, то этим также нужно пренебречь и считать площади независимо.
Входные данные
В первой строке входного файла находятся число T — количество тестов (1 ≤ T ≤ 105). Далее следуют описания тестов. В первой строке каждого описания содержится 4 числа x1, y1, x2, y2, характеризующие координаты концов первого отрезка. Во второй строке — x3, y3, x4, y4, описывающие второй отрезок. В третьей строке записаны три числа x0, y0, R — координаты центра круговой площадки и её радиус. Все числа целые, по модулю не превосходящие 1 000. Радиус положителен.
Гарантируется, что отрезки невырождены и не пересекаются с круговой площадкой. Также гарантируется, что они не имеют общих внутренних точек.
Выходные данные
Для каждого теста выведите координаты точки внутри круга, удовлетворяющей условию задачи. Если таких точек несколько, то выведите любую из них. Координаты следует выводить с как можно бóльшим числом знаков после десятичной точки. Соответствующая сумма площадей должна отличаться от правильного ответа по абсолютной или относительной величине не больше чем на 10 - 6.
Примеры тестов
Входные данные
1
0 0 1 0
0 0 -1 0
0 2 1
Выходные данные
0.0000000000 3.0000000000
Выбрано
:
|