Просека — эта такая прямая линия, которая проходит через лес (то есть деревья есть как с одной стороны от этой линии, так и с другой), и при этом она не проходит ни через одно из деревьев леса, а также не касается деревьев. Будем говорить, что лес является дремучим, если в нем нет ни одной просеки.
На плане леса все деревья изображаются кругами. Никакие два круга не пересекаются и не касаются друг друга. Требуется по этому плану определить, является ли лес дремучим.
Во входном файле содержится сначала целое число N — количество деревьев (1N200). Затем идет N троек чисел, задающих деревья. Первые два числа задают координаты центра, а третье — радиус. Все данные задаются точно, и выражаются вещественными числами, не более чем с 2 знаками после десятичной точки, по модулю не превосходящими 1000.
В первой строке выходного файла должно содержаться сообщение YES, если лес является дремучим, и NO иначе. Во втором случае вторая строка выходного файла должна содержать координаты двух точек, через которые проходит просека. Все координаты нужно выводить с восемью знаками после десятичной точки, координаты не должны превышать 2000, и расстояние между выданными точками должно быть не меньше 100.
3
0.00 30.00 25.00
0.00 -30.00 25.00
40.00 0.00 16.00
NO
-833.3333340000 -552.7707973875
833.3333340000 552.7707973875
3
0.00 30.00 29.00
0.00 -30.00 29.00
40.00 0.00 19.00
YES
На территории будущей стройки растут три дерева. Фирма получила разрешение на строительные работы с условием, что два (любых) дерева будут сохранены. Прораб хочет построить забор треугольной формы так, чтобы внутри него оказалось ровно два дерева.
Деревья на плане изображаются кругами, которые попарно не вложены друг в друга и не пересекаются (но могут касаться).
Напишите программу, которая по введенной информации о деревьях определит, возможно ли построить такой забор, и, если да, то какое дерево окажется не огорожено.
Вводится информация о трех деревьях: для каждого дерева координаты центра и радиус круга, изображающего это дерево на плане. Все числа целые, не превосходящие по модулю 3000. Радиус – натуральное число.
Выведите одно число – номер дерева (деревья нумеруются начиная с 1 в порядке задания их во входных данных), которое окажется не огорожено. Если забор треугольной формы, огораживающий ровно два дерева, построить невозможно, выведите число 0. Если существует несколько решений, выведите любое.
Как известно, к северу от Москвы находится много горнолыжных трасс, расположенных на холмах Клинско-Дмитровской гряды. Один из курортов в связи с финансовым кризисом решил расширить спектр услуг, предлагая трассы для катания не только на лыжах и сноубордах, но и санные трассы.
У хозяев курорта имеется топографическая карта территории, высоты на которой отображены с помощью контуров, каждый из которых представляет собой окружность. У каждой окружности указана высота поверхности, прилегающей к внутреннему контуру этой окружности. Вся территория, которая не находится внутри какой-либо окружности, имеет высоту 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 |
Вася заасфальтировал один прямоугольный треугольник, а Петя забетонировал другой прямоугольный треугольник. Катеты каждого из треугольников параллельны осям координат. Необходимо определить, забетонировал ли Петя хотя бы одну заасфальтированную точку.
Вам даны 8 целых чисел: x1, y1, a1, b1, x2, y2, a2, b2, где (x1, y1) - координаты прямого угла первого треугольника, а остальные две вершины имеют координаты (x1 + a1, y1) и (x1, y1 + b1). Аналогично, (x2, y2) - координаты прямого угла второго треугольника, а остальные две вершины имеют координаты (x2 + a2, y2) и (x2, y2 + b2). Каждое число по модулю не превосходит 109 и может быть равно нулю.
Выведите YES, если Петя забетонировал хотя бы одну заасфальтированную точку, и NO в противном случае.
3 3 1 1 3 3 -2 -2
YES
3 4 7 -4 6 6 -20 1
NO
Петя нарисовал на клетчатом листке бумаги красивый рисунок прямоугольной формы. Его младшему брату Васе тоже захотелось порисовать, поэтому он вырезал из того же листка бумаги другой прямоугольник. При этом он не делал лишних разрезов, то есть в результате в листке осталась прямоугольная дырка. Кроме того, линии разреза не проходили (даже частично) по границам рисунка Пети. Более того, по границам рисунка не проходили даже продолжения линий разреза.
Ваша задача – по данным о расположении рисунка и прямоугольной дырки определить, испортил ли Вася рисунок старшего брата, другими словами, есть ли на вырезанном Васей прямоугольнике хотя бы маленький фрагмент рисунка Пети.
Вам даны 8 целых чисел - x1, y1, x2, y2, x3, y3, x4, y4, где (x1, y1) - координаты левого нижнего угла рисунка Пети, (x2, y2) - координаты правого верхнего угла рисунка. Аналогично, (x3, y3) - координаты левого нижнего угла вырезанного Васей прямоугольника, (x4, y4) - координаты правого верхнего угла вырезанного прямоугольника. Гарантируется, что данные прямоугольники невырождены (x1 < x2, y1 < y2 и аналогичные неравенства для второго набора координат). Листок был не очень большим, поэтому каждое число по модулю не превосходит 104.
Выведите YES, если Вася испортил рисунок, и NO в противном случае.
1 1 2 2 3 3 4 4
NO
1 1 3 3 2 2 4 4
YES
1 1 4 4 2 2 3 3
YES