Яндекс.Алгоритм 2011: Финал |
---|
Закончено |
Множество точек на плоскости называется хорошим, если для любых двух точек выполняется хотя бы одно из трех условий:
На плоскости задано множество из n точек. Найдите любое хорошее надмножество этого множества размером не более 2·105 точек.
В первой строке записано целое число n (1 ≤ n ≤ 104) — количество точек в исходном множестве. Следующие n строк описывают точки множества. Каждая строка содержит два целых числа xi и yi ( - 109 ≤ xi, yi ≤ 109) — координаты очередной точки. Гарантируется, что все точки различны.
В первой строке выведите количество точек m (n ≤ m ≤ 2·105) в хорошем надмножестве, в следующих m строках выведите сами точки. Координаты точек не должны превосходить 109 по абсолютной величине. Обратите внимание, что минимизировать m не требуется, достаточно найти любое хорошее надмножество заданного множества, размер которого не превосходит 2·105.
Все точки в надмножестве должны иметь целые координаты.
2
1 1
2 2
3
1 1
2 2
1 2
Название |
---|