Ленивый Вася и релиз Half-Life 3

Примеры

Площадь треугольника

Примеры

Сумма штрафа

Полярный угол точки

Даны два числа - координаты точки, не совпадающей с началом координат. Найти полярные координаты точки, не совпадающей с началом координат.

Входные данные
Во входной строке содержится два целых числа - координаты точки. Числа целые, по модулю не превышающее 1000.

Выходные данные
Одно число - величина ее полярного угла (в радианах). Значение полярного угла должно принадлежать интервалу [0; 2*π).

Примеры

Треугольник. Поиск вершины по положению центроида

Точка G – центр пересечения медиан треугольника (центроид) АВС_.
Найдите абсциссу вершины C (координату x), если известно:
- координаты точек A и B;
- координата точки D, лежащей на прямой ВС;
- точка G лежит на прямой ED (координаты точки E известны);
- для координат выполняются условия: Ax<Cx<Bx;
Входные данные: в 1-й строке вводятся значения Ax, Ay, Bx, By Dx,Dy, Ex, Ey – координаты точек A, B, D, E
Все значения целые числа в интервале [-1000;1000].
Выходные данные: ответ на задание с точностью не менее 10^-5.
Пример:

Поиск вершины по центру описанной окружности (O)

Точка O – центр описанной окружности треугольника АВС_.
Найдите абсциссу вершины C (координату x), если известно:
- координаты точек A и B;
- координата точки D, лежащей на прямой ВС;
- точка O лежит на прямой ED (координаты точки E известны);
- для координат выполняются условия: Ax<Cx<Bx;
Входные данные: в 1-й строке вводятся значения Ax, Ay, Bx, By Dx,Dy, Ex, Ey – координаты точек A, B, D, E
Все значения целые числа в интервале [-1000;1000].
Выходные данные: ответ на задание с точностью не менее 10^-5.
Пример:

Кардиоида

Кардиоида-- плоская алгебраическая кривая 4-го порядка, которая описывается фиксированной точкой окружности радиуса , катящейся по неподвижной окружности с таким же радиусом

В прямоугольной декартовой системе координат уравнение кривой имеет вид:

Найдите координаты точки пересечения кардиоиды и отрезка EF, если известно:
- коэффициент кардиоиды a;
- координаты вершин отрезка EF;
гарантируеся, что одна из вершин отрезка лежит внутри кардиоиды, а другая снаружи.
Рассмотрим функцию F(x,y,a)= (x²+y²+2ax)²-4a²(x²+y²). Если для точки M с координатами (x,y) F(x,y,a)<0, то точка M лежит внутри кардиоды с параметром a. Если значение функции будет положительным, то точка M лежит снаружи.

Эллипс и отрезок

Найдите координаты точки пересечения эллипса и отрезка, если известно:
- координаты точек фокусов эллипса A, B;
- R - сумма расстояний от точки эллипса до фокусов;
- координаты вершин отрезка EF;
гарантируеся, что одна из вершин отрезка лежит внутри эллипса, а другая снаружи
Входные данные:
-в 1-й строке вводятся значения Ax, Ay, Bx, By, R – координаты точек A, B и сумма расстояний R
-в 2-й строке вводятся значения Ex, Ey, Fx, Fy – координаты вершин отрезка  EF
Все значения целые числа в интервале [-1000;1000].
Выходные данные:
1 строка  - абцисса точки пересечения (координата x), с точностью не менее 10^-5 
2 строка  - ордината точки пересечения (координата y), с точностью не менее 10^-5 

Пример:

Расстояние между отрезками - 3

Найдите расстояние между отрезками AB и CD. Отрезки заданы декартовыми координатами границ в пространстве.
Расстояние между отрезками - минимальное расстояние между точками X,Y, где \(X \in [A,B], \ Y\in[C,D]\).
Входные данные
В 1-й строке вводятся шесть чисел, разделённых пробелами. Вначале вводятся координаты точки A (A_x,A_y,A_z),  затем координаты точки B (B_x,B_y,B_z).
В 2-й строке вводятся шесть чисел, разделённых пробелами. Вначале вводятся координаты точки C (C_x,C_y,C_z),  затем координаты точки D (D_x,D_y,D_z).
Выходные данные
Выводится одно число - расстояние между отрезками AB, CD.
Расстояние необходимо найти с точностью не менее 10^-6.
Пример 1:

Точка пересечения медиан

Точка пересечения медиан

1 1 2 4 3 2

2.00000 2.33333

2 4 3 2 1 1 

2.00000 2.33333

Вписанная окружность

Вписанная окружность

2.12132 2.292893 0.65493

10 0 12 2 14 5

 11.878925  2.099258  0.1557984

Точка пересечения двух прямых

Точка пересечения прямых

0 0 1 1
1 0 -1 2

1  0.50  0.50

1 2 3 4
0 3 4 7

0

1 2 3 4
3 4 1 2

Описанная окружность

Описанная окружность

1.50000 2.50000 1.58114

10 0 12 2 14 5

-0.50000 12.50000 16.32483

Приданое для Василисы

Приданое для Василисы

0 1 -2 3 8 3

-1 2 10 11 0 1

  0.1600294

Приданое для Ирины

Приданое для Ирины

0 1 -2 3 8 3

-1 2 10 11 0 1

 0.0739834

Описанная окружность

Описанная окружность

1.50000 2.50000 1.58114

10 0 12 2 14 5

-0.50000 12.50000 16.32483

ЛА-0107a_Расстояние от точки до прямой-2

Расстояние от точки до прямой-2

Примеры

1 10 6

10 1 6 

 -1

Вид из окна

На протяжении многих лет Вася работает программистом в одной очень большой и очень из- вестной компании. Эта компания обеспечивает своих сотрудников всем необходимым для приятной и плодотворной работы: бесплатными обедами, транспортом от дома до места работы и многим, многим другим. И вот в один прекрасный солнечный день Вася понял, что ему очень наскучил вид из окна его офиса, и ему нужно, чтобы за окном было что-то новое и прекрасное. А что может быть лучше чудесного горного пейзажа? Придя к этой мысли, Вася попросил своего менеджера подобрать себе новый офис с красивым видом на горы.

В той местности, где располагается офис Васи, каждая гора принадлежит некоторой горной цепи. Так как Васе хочется, чтобы вид из окна его офиса был идеальным, то он попросил подобрать себе такой офис, чтобы никакие две горные цепи, видимые из окна, не пересекались. Менеджер Васи нашел прекрасный новый офис, из которого видно N горных цепей, но он никак не может определить, понравится ли Васе вид из окна этого офиса. Помогите ему!

Более формально, вид из окна офиса представляет собой набор горных цепей, пронумерованных от 1 до N, где горная цепь с номером i представляет собой ломаную на плоскости из li звеньев с вершинами в точках (x_i,j , y_i,j ), причем для любых i, j выполнено x_i,j < x_i,j+1.

Кроме этого, окно в офисе имеет фиксированную ширину, поэтому все горные цепи начинаются и заканчиваются на одной вертикали, то есть существуют такие числа A и B, что для любого номера i горной цепи выполнено x_i,0 = A, x_i,li = B.

Отметим, что из определения горной цепи следует, что для любого значения абсциссы A <= x <= B на ломаной с номером i существует единственная точка (x, yi(x)) с этим значением абсциссы, при- надлежащая этой ломаной. Будем говорить, что горная цепь i находится строго выше горной цепи j в точке x, если выполнено строгое неравенство y_i(x) > y_j (x).

Естественно считать, что цепь под номером i пересекается с цепью под номером j, если су- ществуют такие два значения абсциссы x1, x2, что цепь i находится строго выше цепи j в точке x1, но при этом цепь j находится строго выше цепи i в точке x2, то есть выполнены неравенства y_i(x₁) > y_j (x₁) и y_j (x₂) > y_i(x₂). Обратите внимание на поясняющие рисунки, расположенные в примечании к задаче.

Вам необходимо определить, подойдет ли подобранный офис Васе, и, если нет, то найти любую пару пересекающихся горных цепей.

Формат входных данных 
В первой строке входных данных через пробел идут два целых числа: A и B (−10⁹<=A < B<=10⁹ ).
Во второй строке входных данных находится единственное число N — количество горных цепей, видимых из окна подобранного менеджером Васи офиса (1 <= N <= 100 000).
Далее следуют описания N горных цепей. В первой строке i-го описания содержится число l_i => 1 — количество звеньев ломаной, из которых состоит соответствующая горная цепь. В следую- щих li + 1 строках описания содержатся два целых числа — координаты (x_i,j , y_i,j ) вершин ломаной (0 <= j <= l_i). Суммарное число звеньев всех ломаных не превосходит 200 000.
Гарантируется, что для каждой горной цепи вершины соответствующей ей ломаной идут во входных данных в порядке возрастания абсциссы, причем для любого i выполнено x_i,0 = A, x_i,li = B.

Формат выходных данных 
Если же офис подходит Васе, то есть никакие две горные цепи из входных данных не пересека- ются, в единственной строке выходных данных выведите слово "Yes" (без кавычек).
Иначе выведите в первой строке слово "No" (без кавычек), а на следующей строке выведите два числа — номера двух пересекающихся горных цепей. Горные цепи нумеруются согласно их появлению во входных данных, начиная с 1.

Примеры

Fencing the Herd

Вращающаяся пластина

Мальчик Вася очень любит геометрию. Кроме того, ему очень нравится забивать гвозди в доску. Сегодня он изучает свою любимую металлическую пластину, которую он собирается прибить к деревянной доске.

Пластина имеет форму, ограниченную многоугольником без самопересечений и самокасаний. В первой вершине многоугольника пластина имеет маленькую петлю.

Сначала Вася кладет пластину на доску, лежащую на горизонтальном столе, и прибивает ее гвоздем к пластине через петлю в первой вершине. Вбитый гвоздь жестко закрепляет положение первой вершины, однако позволяет пластине вращаться вокруг нее.

Теперь Вася хочет забить в доску еще один гвоздь, который бы ограничил вращение пластины, но он еще не решил куда. Он наметил m возможных позиций, куда он хотел бы забить гвоздь, и для каждой из них хочет узнать, на какой угол он сможет поворачивать свою пластину, если забьет в доску гвоздь в этой точке. При этом как только пластина касается гвоздя, дальше ее поворачивать нельзя.

Формат входных данных
В первой строке входного файла задано число n (3 ≤ n ≤ 2 000) — количество вершин многоугольника. В следующих n строках заданы координаты вершин многоугольника в порядке обхода. В следующей строке задано число m (1 ≤ m ≤ 2 000) — количество точек, которые Вася рассматривает как возможные положения второго гвоздя. В следующих m строках заданы координаты этих точек. Все эти точки находятся снаружи от исходного положения пластины. Все координаты во входном файле целые и не превосходят 10⁶ по модулю.

Формат выходных данных
Выходной файл должен содержать m строк. В i-й строке выведите два вещественных числа α_i и β_i , где α_i — максимальный угол в градусах, на который можно повернуть пластину по часовой стрелке, если Вася забьет гвоздь в i-ю точку, а β_i — максимальный угол в градусах ,на который в этом случае можно повернуть пластину против часовой стрелки. Если гвоздь не мешает пластине поворачиваться, выведите α_i = β_i = 360. Ответ считается верным, если его абсолютная или относительная погрешность относительно правильного не превосходит 10⁻⁶ .
 

Поиск вершины по ортоцентру (H)

Точка H – центр пересечения высот треугольника (ортоцентр) АВС_.
Найдите абсциссу вершины C (координату x), если известно:
- координаты точек A и B;
- координата точки D, лежащей на прямой ВС;
- точка H лежит на прямой ED (координаты точки E известны);
- для координат выполняются условия: Ax<Cx<Bx;
Входные данные: в 1-й строке вводятся значения Ax, Ay, Bx, By Dx,Dy, Ex, Ey – координаты точек A, B, D, E
Все значения целые числа в интервале [-1000;1000].
Выходные данные: ответ на задание с точностью не менее 10^-5.
Пример:

Лестницу в треугольник

На плоскости дана геометрическая фигура "лестница". Она имеет N ступенек, которые заданы положительными координатами. Каждая ступень имеет свою высоту и ширину. Требуется найти прямую, которая отсекает от некоторых ступеней "лестницы" треугольники так, что из полученных фигур можно сложить прямоугольный треугольник такой же площади, что и исходная фигура. Разрешается, чтобы отсекаемые от ступеней треугольники соприкасались только вершинами (но не сторонами).

Формат входных данных:
В первой строке дано число 0 <= N <= 1000. Далее записаны N строк. Каждая строка содержит два целых чисел через пробел 0 < x_i, y_i < 10⁶ - координаты вершины i-й ступени (ступени перечисляются в порядке сверху вниз, слева направо).

Формат выходных данных:
Ответ содержит одну строку: два числа через пробел - высота и ширина получившегося прямоугольного треугольника. Если существует несколько решений, то вывести любое. Результат выводится с точностью до четырех десятичных знаков после запятой. В случае, когда решение отсутствует, вывести два ноля через пробел

Примечание

Центр тяжести

По координатам вершин многоугольника требуется найти координаты его центра тяжести. Стороны многоугольника друг с другом не соприкасаются (за исключением соседних - в вершинах) и не пересекаются. Площадь многоугольника не равна нулю.

Ограничения: число вершин 3 <= N <= 100 000, координаты вершин в декартовой системе координат целые и по модулю не превосходят 20 000.

Входные данные
В первой строке находится число N, в следующих N строках - пары чисел - координаты точек. Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник.

Выходные данные
Вывести два числа с двумя знаками после запятой - координаты центра тяжести.

Перекладывание дорог

В городе N есть \(m\) асфальтированных дорог, \(i\)-я дорога представляет собой отрезок между двумя точками \(A_{i}\) и \(B_{i}\) с координатами \((x^{A}_{i}, y^{A}_{i})\) и \((x^{B}_{i}, y^{B}_{i})\) соответственно.

В рамках тестирования новой технологии, которая позволяет переместить дорогу, мэр города N может демонтировать ровно одну любую дорогу и построить в любом месте ровно одну новую дорогу из полученного при демонтаже асфальта, при этом длина новой дороги должна не превосходить длину демонтированной дороги.

Проанализировав бюджет города, мэр понял, что в будущем он сможет обслуживать ровно три асфальтированные дороги.

Поэтому в рамках программы благоустройства мэр хочет выбрать три дороги, которые останутся асфальтированными, а также, возможно, переложить одну из них. Остальные асфальтовые дороги придется превратить в грунтовые. После этого три получившиеся дороги должны образовывать связный асфальтированный участок, то есть между любыми двумя асфальтированными точками должно быть можно добраться по асфальтированным дорогам.

Теперь мэр хочет понять, сколькими способами можно успешно завершить благоустройство города N: выбрать три дороги, чтобы выполнялись описанные условия.

Формат входных данных
В первой строке входных данных дано целое число \(m\) — количество асфальтированных дорог в городе (\(3 \leq m \leq 100\)).

Далее даны \(m\) строк. В \(i\)-й строке записаны четыре целых числа: \(x^{A}_{i}\), \(y^{A}_{i}\), \(x^{B}_{i}\), \(y^{B}_{i}\) — координаты точек \(A_{i}\) и \(B_{i}\) начала и конца \(i\)-й дороги соответственно.

Все координаты точек целые и по абсолютному значению не превосходят \(10^4\). Конечные точки любой дороги различны.

Формат выходных данных
В единственной строке выходных данных выведите одно целое число \(k\) — количество способов выбрать три дороги так, чтобы можно было успешно завершить благоустройство города N.

В примере из условия, чтобы успешно завершить благоустройство города N, можно выбрать три дороги одним из трех способов:

1. дороги \(\{1, 2, 3\}\) с координатами \((1, 1)-(2, 3)\), \((1, 3)-(2, 1)\), \((3, 1)-(4, 3)\) соответственно, и переложить дорогу \(3\), например, на новые координаты \((1, 4)-(2, 2)\)

2. дороги \(\{1, 2, 4\}\) с координатами \((1, 1)-(2, 3)\), \((1, 3)-(2, 1)\), \((2, 6)-(3, 6)\) соответственно, и переложить дорогу \(4\), например, на новые координаты \((1, 2)-(2, 2)\)

3. дороги \(\{2, 3, 4\}\) с координатами \((1, 3)-(2, 1)\), \((3, 1)-(4, 3)\), \((2, 6)-(3, 6)\) соответственно, и переложить дорогу \(4\), например, на новые координаты \((2, 1)-(3, 1)\)

Иллюстрация к способу a)
Перекладывание \(3\)-й дороги с координат \((3, 1)-(4, 3)\) на новые координаты \((1, 4)-(2, 2)\)

Иллюстрация к способу b)
Перекладывание \(4\)-й дороги с координат \((2, 6)-(3, 6)\) на новые координаты \((1, 2)-(2, 2)\)

Иллюстрация к способу c)
Перекладывание \(4\)-й дороги с координат \((2, 6)-(3, 6)\) на новые координаты \((2, 1)-(3, 1)\)

Mountains

**Обратите внимание: время на тест для этой задачи 5s, в 2.5 раза больше, чем обычно. Предельный размер памяти также увеличен в два раза по сравнению с умолчанием.

Имеется \(N\) (\(1 \leq N \leq 2000\)) гор в ряд на ферме Джона Это может быть выражено как массив высот \(h_1,h_2,\dots,h_N\). Для горы \(i\), Вы можете увидеть другую гору \(j\) если нет гор строго выше чем линия взгляда, соединяющая горы \(j\) и \(i\). Формально, для двух гор \(i < j\), они могут видеть друг друга, если не существует такого \(k\) \(i < k < j\) и \((k, h_k)\) выше чем отрезок, соединяющий \((i, h_i)\) и \((j, h_j)\). Имеется \(Q\) (\(1 \leq Q \leq 2000\)) изменений высот, когда высота одной горы возрастает. Определите общее количество неупорядоченных пар гор, которые могут видеть друг друга после каждого изменения.

ПРМЕР ВВОДА:

5
2 4 3 1 5
3
4 3
1 3
3 2

Farm Painting

После нескольких суровых зим, Фермер Джон решил, что пришло время покрасить свою ферму. Ферма состоит из N (1 <= N <= 50,000) отгороженных пастбищ, каждое из которых может быть описано прямоугольником на 2D плоскости со сторонами, параллельными осям X и Y.
Пастбища могут содержаться один внутри другого, но их изгороди не могут пересекаться. Поэтому, если два пастбища покрывают одну и ту же область на 2D плоскости, то одно должно содержаться внутри другого.
ФД понимает, что пастбище, содержащееся внутри другого, не видимо снаружи. Поэтому он хочет красить изгороди только тех пастбищ, которые не содержатся внутри других пастбищ.
Определите общее количество пастбищ, изгороди которых он должен покрасить.
PROBLEM NAME: painting
Формат входных данных
* Строка 1: Количество изгородей, N.
* Строки 2..1+N: Каждая строка описывает изгородь 4-мя целыми числами x1, y1, x2, y2 (разделенных одиночными пробелами), где (x1,y1) - левый нижний угол изгороди, (x2,y2) - правый верхний уго изгороди. Все координаты в диапазоне 0..1,000,000.
Формат выходных данных
* Строка 1: Количество пастбищ, которые не содержатся внутри других пастбищ.
Примечание
Пастбище 3 содержится внутри пастбища 1, поэтому ответ 2.

Tied Down

Беси одна из тех коров, которые любят создавать проблемы. Во избежание этого Фермер Джон решил привязать Беси к изгороди длинной веревкой. Если смотреть сверху, изгородь представляет N столбов (1 <= N <= 10), которые расположены вдоль вертикальной прямой. Беси находится в позиции (bx,by) находящейся справа от это вертикальной линии. Веревка, которой ФД привязывает Беси описывается последовательностью из M отрезков прямой, (3 <= M <= 10,000), где первый отрезок начинается в позиции Беси, и последний отрезок заканчивается в позиции Беси. Никакой из столбов не лежит ни на одном из этих отрезков. Однако отрезки могут пересекаться, и многие отрезки могут пересекаться в своих конечных точках.
Пример такой сцены, вид сверху:

Чтобы помочь Беси освободиться, подружки стащили пилу из амбара. Определите минимальное количество столбов, которые они должны спилить, для того, чтобы Беси могла освободиться (то есть она сможет убежать, И никакой из отрезков веревки не зацепился, ни за какой из столбов)
Все (x,y)-координаты на вводе (столбы изгороди, Беси, конечные точки отрезков), есть целые числа в диапазоне 0..10,000. Все столбы имеют одну и ту же x-координату, bx больше этой величины.
PROBLEM NAME: tied
Формат входных данных
* Строка 1: Четыре целых числа, разделенных пробелами: N, M, bx, by.
* Строки 2..1+N: Строка i+1 содержит разделенные пробелами x и y координаты столба i.
* Строки 2+N..2+N+M: Каждая из этих M+1 строк содержит, по очереди, x и y координаты точки веревки. Первая и последняя точки всегда совпадают с координатами Беси (bx,by).
Формат выходных данных
* Строка 1: Минимальное количество столбов, которое нужно удалить, Чтобы корова смогла убежать, двигаясь вправо.
Примечание
Удаление столба 1 или столба 2 приводит к желаемому результату.

66165

Ученики Школы №1232 обожают все праздники в году, так как школа всегда организует очень много всяких интересных активностей: конкурсов, викторин, квизов и так далее. И в очередном из праздников учителя захотели сделать интересную викторину: ученики находились на поле, когда начинала играть музыка, они перемещались в хаотичном порядке, когда заканчивала, через колонки называлось число K, что означало, что ученикам нужно было объединиться в группы из K человек, кто не успел, выбывали из игры. Далее игра снова продолжалась с теми учениками, которые остались.
Проблемой этой игры составлял выбор – с кем объединиться каждому ученику, так как абсолютно все ученики были дружелюбными и знали друг друга в школе.
Учителя всегда интересуются тем, как поведут себя ребята в стрессовой ситуации, потому запустили заранее дрон над полем, картинка с которого передавалась в программу, которая преобразовывала после окончания музыки снимок учеников сверху в набор координат в плоскости OXY. Далее находилась пара самых близких друг к другу двух учеников.
Напишите программу, которая на основании преобразованного снимка в координаты, выведет имена двух учеников, которые наиболее близки по расстоянию друг к другу на момент окончания музыки.

Входные данные
На первой строке подаётся целое число N (2 <= N <= 10⁶).
Далее на N строках подаются данные каждого ученика: его имя, координата X, координата Y, все через пробел (координаты всегда целые).
Координаты в диапазоне от -10⁴ до 10⁴.
Выходные данные
Вывести на одной строке через пробел два имени учеников, которые наиболее приближены друг к другу на всём поле, чем все остальные. Имена выводить в алфавитном порядке.
Примечание:
·имена учеников всегда на английском языке для удобстваобработки;
·имена учеников всегда состоят только из одного слова итолько из букв латинского алфавита, без спецсимволов и прочих знаков;
·на одной координате не может быть двух учениководновременно;
·если пар подходящих для ответа несколько, то вывести ту,которая максимально приближена к координате (0;0);
·если и таких пар несколько, то вывести любую.

Соединение точек

«Соединение точек» – это игра для одного игрока. Игровое поле строится следующим образом. Выбираются два целых числа, каждое из которых больше 2, которые обозначаются g и r. Затем на плоскости рисуются четыре точки в вершинах квадрата, две верхние из них становятся зелеными точками, а две нижние – красными. Далее внутри квадрата рисуются зеленые и красные точки таким образом, что никакие три точки, включая вершины квадрата, не лежат на одной прямой. Процесс продолжается до тех пор, пока общее количество зеленых точек не станет равным g, а количество красных точек – равным r.

После того, как игровое поле нарисовано, игрок начинает соединять точки. Две точки можно соединять отрезком, соблюдая следующие условия:
*соединяются только две точки одного цвета;
*отрезок, соединяющий точки, не пересекает никакой из ранее нарисованных отрезков (кроме как по концам отрезков).

Будем считать, что две точки u и v принадлежат одной компоненте, если от u до v можно дойти по нарисованным отрезкам.

Цель игры – соединить все зеленые точки в одну компоненту с помощью (g – 1) отрезков, а все красные точки – в другую компоненту с помощью (r – 1) отрезков. Можно доказать, что при вышеописанном способе расположения точек всегда существует способ выиграть игру.

Вам будет задано квадратное игровое поле со стороной s, а также g зелеными и r красными точками. Координаты точек задаются парами целых чисел (x_i, y_i). Зеленые точки пронумерованы числами от 1 до g так, что верхняя левая точка (0, s) имеет номер 1, верхняя правая точка (s, s) – номер 2, а остальные точки – номера от 3 до g (в произвольном порядке). Красные точки пронумерованы числами от 1 до r так, что нижняя левая точка (0, 0) имеет номер 1, нижняя правая точка (s, 0) – номер 2, а остальные точки – номера от 3 до r (в произвольном порядке).



На рисунке показан пример игры, где зеленые точки соединены в одну компоненту, а красные точки – в другую.

Легко видеть, что никакие три точки на рисунке не лежат на одной прямой, и никакие два отрезка не пересекаются, кроме как по концам.
Задание
Напишите программу, которая по заданным координатам g зеленых точек и координатам r красных точек находит способ, как нарисовать (g – 1) зеленых отрезков и (r – 1) красных отрезков таким образом, чтобы все зеленые точки принадлежали одной компоненте, а все красные точки – другой, и никакие два отрезка не пересекались.

Ограничения
3≤g≤50000,g – количество зеленых точек 
3≤r≤50000
0<s≤200000000,r – количество красных точек

Входные данные
На вход Вашей программы поступают данные в следующем формате:

СТРОКА 1: Содержит целое число g.

СЛЕДУЮЩИЕ g
СТРОК: Каждая строка содержит два целых числа – координаты xi и yi каждой из g зеленых точек, начиная с точки с номером 1 и заканчивая точкой с номером g. Эти два числа разделены пробелами.

СТРОКА g + 2: Содержит целое число r.

СЛЕДУЮЩИЕ r СТРОК: Каждая строка содержит два целых числа – координаты xi и yi каждой из r красных точек, начиная с точки с номером 1 и заканчивая точкой с номером r. Эти два числа разделены пробелами.

Выходные данные
Ваша программа должна вывести (g – 1) + (r – 1) строк, каждая из которых описывает один отрезок, соединяющий две точки.

Каждая строка должна содержать два целых числа и один символ, разделенные пробелом. Числа представляют собой номера точек, соединенных этим отрезком. Если точки зеленые, то последним символом в строке должен быть g, если точки красные, то последним символом в строке должен быть r.

Ни порядок, в котором выводятся отрезки, ни порядок точек в строке не имеют значения.

Замечание
Если существует несколько маршрутов товароперевозок, удовлетворяющих всем указанным требованиям, выведите любой из них.