Будем говорить, что два отрезка образуют L-фигуру, если угол между ними составляет 90˚ и конец одного отрезка совпадает с концом другого. На плоскости заданы N отрезков, занумерованных от 1 до N. Требуется определить количество различных L-фигур, образованных этими отрезками. L-фигуры считаются различными, если они содержат отрезки с разными номерами.
Первая строка содержит натуральное число N (1 ≤ N ≤ 5 000) – количество отрезков. Каждая из следующих N строк описывает один отрезок и содержит 4 целых числа x1, y1, x2, y2 (-10 000 ≤ x1, y1, x2, y2 ≤ 10 000), где (x1, y1) и (x2, y2) – концы отрезка. Конечные точки отрезка не совпадают.
Необходимо вывести одно число — количество различных пар отрезков, образующих L-фигуру.
Есть прямоугольный стол для игры в бильярд размером \(N\)x\(M\). Стол расположен в системе координат так, что его углы находятся в точках с координатами (0,0), (\(N\),0), (\(N\),\(M\)), (\(M\),0).
На столе лежат черный и белый шары. Игрок ударяет по черному шару, задавая ударом направление его движения. Шар летит в заданном направлении, отскакивая от стенок стола по закону отражения. Когда черный шар ударяет по белому шару, то черный шар останавливается, а белый начинает двигаться в том направлении, куда летел в момент удара черный. После этого белому шару запрещается ударять черный шар.
Задача игрока — загнать белый шар в одну из луз, расположенных в углах стола. При этом до попадания в лузу черный и белый шары должны удариться о стенки стола суммарно как можно меньше раз, но не более \(K\) раз.
Сначала вводятся размеры стола \(N\) и \(M\) (3≤\(N\)≤1000, 3≤\(M\)≤1000). Далее записано число K (0≤K≤200). Затем записано две пары чисел \(X_1\), \(Y_1\), \(X_2\), \(Y_2\) – начальные координаты черного шара и начальные координаты белого шара (1≤\(X_1\)≤\(N\)–1, 1≤\(Y_1\)≤\(M\)–1, 1≤\(X_2\)≤\(N\)–1, 1≤\(Y_2\)≤\(M\)–1). Гарантируется, что начальные положения шаров не совпадают, и изначально шары находятся строго внутри стола.
Все числа целые.
Выведите минимальное суммарное количество ударов черного и белого шаров о стенки стола до попадания белого шара в лузу. Если попасть белым шаром в лузу, сделав не более K ударов, невозможно, выведите –1 (минус один).
4 4 3 2 1 2 3
1
4 4 200 1 1 1 3
-1
5 4 3 4 1 4 3
3
5 4 0 3 2 4 3
0
В одном городе недавно запустили автобусную сеть. Однако, плата за проезд для жителей этого города показалась чрезмерной. И несознательные граждане, вместо того, чтобы покупать билет, стали договариваться с водителем и ездить за полцены. Конечно, городская казна понесла серьезные убытки, и было решено взять на работу нескольких контролёров. По уставу, каждый контролёр должен стоять на одном месте и останавливать подозрительные автобусы с целью проверки билетов.
Для повышения эффективности труда контролёров начальство хочет, чтобы через каждую точку, в которой находится контролёр, проходили маршруты всех автобусов. С другой стороны, нельзя ставить нескольких контролёров в одной точке, чтобы они не отвлекались от выполнения своих обязанностей. Наконец, третья сторона, независимый профсоюз, требует от городской администрации принять на работу максимальное количество контролёров.
Для простоты предположим, что действие происходит на координатной плоскости. Каждый автобус ездит по границе прямоугольника c ненулевыми сторонами, вершины которого имеют целочисленные координаты, а стороны параллельны осям координат. Требуется выяснить, какое максимальное число контролёров удастся принять на работу, если городское управление милиции, в свою очередь, требует, чтобы каждый контролёр находился в точке с целочисленными координатами.
На первой строке входного файла находится число \(n\) (1 ≤ \(n\) ≤ \(10^4\)) – количество маршрутов. Далее следуют \(n\) строк, на каждой из которых находятся две пары целых чисел – координаты двух противоположных вершин прямоугольника, по которому проходит данный маршрут. Все координаты не превосходят \(10^8\) по абсолютной величине.
Выведите в выходной файл одно число – максимальное количество контролёров, которые смогут обрести работу благодаря этому мероприятию.
1 0 0 1 1
4
Петя и его друг Андрейка только что познакомились с китайской мифологией. Особенно им понравились драконы. Поэтому мальчики решили сделать своих драконов из проволоки. Андрейка взял белую проволоку и согнул из неё дракона Лун-Инь: этот дракон спал, свернувшись клубком на столе. Тогда Петя взял чёрную проволоку и согнул дракона Лун-Ян. Этот дракон ничем не походил на Андрейкиного Лун-Иня. Его тело состояло из отрезков прямых, а когда он спал, то сворачивался в виде плоской замкнутой несамопересекающейся ломаной. Более того, Лун-Ян не ложился плашмя на стол для сна, а вставал перпендикулярно поверхности. Удержать равновесие дракон может только тогда, когда существуют две его различные точки, касающиеся стола, такие что центр масс дракона находится строго между ними.
Вам требуется узнать, сколько было устойчивых положений у дракона, в которых он мог сохранять равновесие во время сна, если известно, что форма ломаной в виде которой дракон спит всегда одна и та же.
В первой строке входного файла содержится число \(n\) (3 ≤ \(n\) ≤ 1000) – количество вершин ломаной и два целых числа \(x_c\) и \(y_c\) – координаты центра масс дракона (-1000 ≤ \(x_c\), \(y_c\) ≤ 1000). В следующих \(n\) строках содержится по два целых числа \(x_i\) и \(y_i\) (-1000 ≤ \(x_i\), \(y_i\) ≤ 1000) – координаты вершин ломаной в порядке обхода против часовой стрелки (ось \(O_X\) направлена вправо, а ось \(O_Y\) – вверх).
В первой строке выходного файла выведите число устойчивых положений дракона.
12 1 2 3 4 2 4 2 3 1 3 1 4 0 4 0 0 1 0 1 1 2 1 2 0 3 0
4
В одной далекой стране ученые обнаружили странное скопление камней. Изучив его, ученые пришли к выводу, что это части старой крепостной стены, имевшей форму окружности. К сожалению, время и вандалы разрушили некоторые части стены.
Чтобы защитить оставшиеся фрагменты стены и продолжить их изучение в спокойной обстановке, ученые хотят обнести фрагменты стены забором из колючей проволоки. Если сделать отдельный забор для каждого фрагмента, будет неудобно переходить от одного фрагмента к другому, поэтому ученые хотят сделать один общий забор, окружающий все фрагменты.
Помогите ученым посчитать минимальную возможную длину забора, чтобы они знали, сколько просить колючей проволоки.
Во входном файле задано два натуральных числа: число фрагментов \(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