Задача №557. Соединение точек
«Соединение точек» – это игра для одного игрока. Игровое поле строится следующим образом. Выбираются два целых числа, каждое из которых больше 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 \le g \le 50 000, g\) – количество зеленых точек
\(3 \le r \le 50 000\)
\(0 \lt s \le 200 000 000, r\) – количество красных точек
На вход Вашей программы поступают данные в следующем формате:
СТРОКА 1: Содержит целое число \(g\).
СЛЕДУЮЩИЕ \(g\) СТРОК: Каждая строка содержит два целых числа – координаты \(x_i\) и \(y_i\) каждой из \(g\) зеленых точек, начиная с точки с номером 1 и заканчивая точкой с номером \(g\). Эти два числа разделены пробелами.
СТРОКА \(g\) + 2: Содержит целое число \(r\).
СЛЕДУЮЩИЕ \(r\) СТРОК: Каждая строка содержит два целых числа – координаты \(x_i\) и \(y_i\) каждой из \(r\) красных точек, начиная с точки с номером 1 и заканчивая точкой с номером \(r\). Эти два числа разделены пробелами.
Ваша программа должна вывести (\(g\) – 1) + (\(r\) – 1) строк, каждая из которых описывает один отрезок, соединяющий две точки.
Каждая строка должна содержать два целых числа и один символ, разделенные пробелом. Числа представляют
собой номера точек, соединенных этим отрезком. Если точки зеленые, то последним символом в строке должен быть \(g\), если точки красные, то последним символом в строке должен быть \(r\).
Ни порядок, в котором выводятся отрезки, ни порядок точек в строке не имеют значения.
Если существует несколько маршрутов товароперевозок, удовлетворяющих всем указанным требованиям, выведите любой из них.
Первая группа тестов: гарантируется, что решения корректно работающие при \(n + m \le 5000\) будут набирать не менее 37 баллов.
Вторая группа тестов: в ней 9 тестов, каждый оценивается независимо в 7 баллов.
3 0 5 5 5 2 1 3 0 0 5 0 3 4