Лука смог приобрести всю коллекцию динозавров из «Шестёрочки» и обнаружил, что в динозаврах есть коммутаторы, поэтому ему захотелось объединить их в одну локальную сеть. Он расставил на декартовой плоскости всю коллекцию, то есть местоположение каждого динозавра задана двумя числами — координатами по осям x и y.
Лука хочет соединить их проводами так, чтобы между любыми двумя динозаврами существовал путь по этим проводам. Луку раздражают спутанные провода, поэтому никакие два провода не должны пересекаться (пересечения в концах отрезков разрешены). Кроме того, у Луки мало денег на покупку проводов, поэтому общее количество проведённых отрезков не должно превышать 2n.
Формат входных данных
Первая строка содержит одно целое число n (1≤n≤103) — количество динозавров.
В следующих 2n строках заданы координаты динозавров. В каждой строке записано одно целое число: первая строка содержит координату по оси x для первого динозавра, вторая строка — координату по оси y для первого динозавра, третья строка — координату по оси x для второго динозавра, и так далее. Таким образом, координата xi для i-го динозавра находится в (2i)-й строке входных данных, координата yi для i-го динозавра находится в (2i+1)-й строке входных данных. Гарантируется, что (−109≤xi,yi≤109), а также никакие два динозавра не находятся в одной точке плоскости.
Формат выходных данных
В первой строке выведите одно число m — количество проведённых проводов, либо число −1, если соединить динозавров описанным в условии способом невозможно.
Если существует подходящее под условие соединение, то в следующих m строках выведите по два целых числа — порядковые номера динозавров, соединённых очередным проводом.
Если решений несколько, можно вывести любое из них.
1 Ответ
Ответ:
Надо занести все точки в массив, затем соединить через LineTo(x1,y1), проверить существуют ли между ними пересечения:
(((x1<=x)and(x2>=x)and(x3<=x)and(x4>=x))or((y1<=y)and(y2>=y)and(y3<=y)and(y4>=y)))
Так же проверяем m <= 2n