Руководство по У.У.Л.П. решило расставить 4-х снайперов на поле особым образом, а именно, чтобы они образовывали прямоугольник. Три снайпера без проблем заняли свои позиции, а четвертый никак не мог найти своей позиции и в поисках ее начал бродить по полю. Первый снайпер предлагал воспользоваться методом Шредингера, ведь существует отличная от нуля вероятность, что снайпер сам найдет нужное место. Второй снайпер предлагал воспользоваться методами аналитической геометрии. А третий снайпер предложил написать программу, которая методом перебора найдет координаты четвертого снайпера.
Шесть чисел: x1, y1, x2, y2, x3, y3 — координаты трех снайперов через пробел. Гарантируется, что все три координаты помещаются в тип longint (int в си).
Выведите координаты четвертого снайпера.
0 1 2 0 0 0
2 1
Вася заасфальтировал один прямоугольный треугольник, а Петя забетонировал другой прямоугольный треугольник. Катеты каждого из треугольников параллельны осям координат. Необходимо определить, забетонировал ли Петя хотя бы одну заасфальтированную точку.
Вам даны 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
На плоскости дана геометрическая фигура "лестница". Она имеет N ступенек, которые заданы положительными координатами. Каждая ступень имеет свою высоту и ширину. Требуется найти прямую, которая отсекает от некоторых ступеней "лестницы" треугольники так, что из полученных фигур можно сложить прямоугольный треугольник такой же площади, что и исходная фигура. Разрешается, чтобы отсекаемые от ступеней треугольники соприкасались только вершинами (но не сторонами).
В первой строке дано число 0 ≤ N ≤ 1000. Далее записаны N строк. Каждая строка содержит два целых чисел через пробел 0 < xi, yi < 106 - координаты вершины i-й ступени (ступени перечисляются в порядке сверху вниз, слева направо).
Файл содержит одну строку: два числа через пробел - высота и ширина получившегося прямоугольного треугольника. Если существует несколько решений, то вывести любое. Результат выводится с точностью до четырех десятичных знаков после запятой. В случае, когда решение отсутствует, вывести два ноля через пробел
Примеры
|
Входные данные |
Выходные данные |
|
2 |
4.0000 4.0000
|
|
2 |
0 0 |
Пастбища Берляндии в опасности. Волки напали на пастбище овец. Пастух решил застрелить всех волков, при этом не убив ни одной овцы. Ружье заряжено бронебойными патронами, поэтому пули пролетают насквозь. Овцы и волки представлены отрезками. Пастух находится в точке (0, 0). Траектория полета пули — луч, выходящий из точки (0, 0). Если траектория пули имеет общуюточку с отрезком, характеризующим животное, то животное умирает. Найдите наименьшее количество выстрелов, необходимое для убийства всех волков. Овцы при этом должны остаться живы.
В первой строке записаны два целых числа N и M (0 ≤ N ≤ 100000, 0 ≤ M ≤ 100000) — количество волков и овец соответственно. Далее следует N+M строк. В каждой строке записано четыре числа X1, Y1, X2, Y2 (−1000 ≤ X1, X2 ≤ 1000, 1 ≤ Y1, Y2 ≤ 1000), описывающие отрезки. Первые N отрезков описывают положение волков, следующие M строк положение овец.
Выведите наименьшее количество выстрелов, необходимое для убийства всех волков. Если невозможно убить всех волков, сохранив овец живыми, то выведите “No solution”.
1 1 5 5 6 7 3 5 8 5
No solution
2 1 1 1 2 3 -5 4 2 2 999 1000 1000 999
1
2
3