--->
144 задач
<---
Источники
#1762
Источники:
[
Командные олимпиады,
Командные чемпионаты школьников Санкт-Петербурга по программированию,
2004,
Задача B
]
Из окружности вырезано некоторое количество фрагментов. Требуется найти минимальную выпуклую оболочку (провести между оставшимися фрагментами хорды).
В одной далекой стране ученые обнаружили странное скопление камней. Изучив его, ученые пришли к выводу, что это части старой крепостной стены, имевшей форму окружности. К сожалению, время и вандалы разрушили некоторые части стены.
Чтобы защитить оставшиеся фрагменты стены и продолжить их изучение в спокойной обстановке, ученые хотят обнести фрагменты стены забором из колючей проволоки. Если сделать отдельный забор для каждого фрагмента, будет неудобно переходить от одного фрагмента к другому, поэтому ученые хотят сделать один общий забор, окружающий все фрагменты.
Помогите ученым посчитать минимальную возможную длину забора, чтобы они знали, сколько просить колючей проволоки.
Входные данные
Во входном файле задано два натуральных числа: число фрагментов \(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
Источники:
[
Командные олимпиады,
Командные чемпионаты школьников Санкт-Петербурга по программированию,
2005,
Задача B
]
ограничение по времени на тест
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
Темы:
[Элементарная геометрия]
[Тернарный поиск]
Источники:
[
Командные олимпиады,
Командные чемпионаты школьников Санкт-Петербурга по программированию,
2006,
Задача E
]
ограничение по времени на тест
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.0 second;
ограничение по памяти на тест
64 megabytes
Руководство по У.У.Л.П. решило расставить 4-х снайперов на поле особым образом, а именно, чтобы они образовывали прямоугольник. Три снайпера без проблем заняли свои позиции, а четвертый никак не мог найти своей позиции и в поисках ее начал бродить по полю. Первый снайпер предлагал воспользоваться методом Шредингера, ведь существует отличная от нуля вероятность, что снайпер сам найдет нужное место. Второй снайпер предлагал воспользоваться методами аналитической геометрии. А третий снайпер предложил написать программу, которая методом перебора найдет координаты четвертого снайпера.
Входные данные
Шесть чисел: x1, y1, x2, y2, x3, y3 — координаты трех снайперов через пробел. Гарантируется, что все три координаты помещаются в тип longint (int в си).
Выходные данные
Выведите координаты четвертого снайпера.
Примеры
Входные данные
0 1 2 0 0 0
Выходные данные
2 1
Рассмотреть прямые, проходящие через какой либо угол. Угол наклона определяется однозначно.
На плоскости дана геометрическая фигура "лестница". Она имеет N ступенек, которые заданы положительными координатами. Каждая ступень имеет свою высоту и ширину. Требуется найти прямую, которая отсекает от некоторых ступеней "лестницы" треугольники так, что из полученных фигур можно сложить прямоугольный треугольник такой же площади, что и исходная фигура. Разрешается, чтобы отсекаемые от ступеней треугольники соприкасались только вершинами (но не сторонами).
Входные данные
В первой строке дано число 0 ≤ N ≤ 1000. Далее записаны N строк. Каждая строка содержит два целых чисел через пробел 0 < xi, yi < 106 - координаты вершины i-й ступени (ступени перечисляются в порядке сверху вниз, слева направо).
Выходные данные
Файл содержит одну строку: два числа через пробел - высота и ширина получившегося прямоугольного треугольника. Если существует несколько решений, то вывести любое. Результат выводится с точностью до четырех десятичных знаков после запятой. В случае, когда решение отсутствует, вывести два ноля через пробел
Примеры
|
Входные данные |
Выходные данные |
|
2 |
4.0000 4.0000
|
|
2 |
0 0 |
2
3Выбрано
:
|