Задача №111899. Разделение королевства
Королевство Флатландия имеет вид бесконечной двумерной плоскости. В королевстве находится \(n\) замков. Для более удобного составления карт в Флатландии была введена Декартова система координат. Известно, что \(i\)-й замок находится в точке с координатами \((x_i+0.5, y_i+0.5)\), где \(x_i\), \(y_i\) - целые числа. Местоположения всех замков попарно различны.
На старости лет король решил разделить на карте королевство между своими сыновьями прямыми, параллельными осям координат. Если прямая параллельна оси \(Ox\), то \(y\) координата у всех точек на прямой должна быть целым числом, иначе \(x\) координата у всех точек должна быть целым числом. В обоих случаях соответствующие целые координаты по модулю не должны превышать \(2 \cdot 10^9\). При этом Его величество хочет, что бы после разделения королевства любые два замка оказались бы в различных частях.
Помогите королю разделить королевство, используя не более чем \(n-1\) прямую. У любой пары прямых должно быть не более одной общей точки.
В первой строке задано целое число \(n\) (\(1 \le n \le 100\,000\)) - количество замков в королевстве. В следующих \(n\) строках записано по два числа \(x_i\) и \(y_i\) (\(-10^9 \le x_i \le 10^9\), \(-10^9 \le y_i \le 10^9\)) - целые части координат замков.
В первой строке выходного файла выведите количество используемых прямых. В следующих строчках выведите сами прямые, по одной в каждой строке. Если прямая параллельна оси \(Ox\), то выведите символ "y", а затем через пробел \(y\) координату всех точек на этой прямой, иначе выведите символ "x", а затем через пробел \(x\) координату всех точек на этой прямой.
4 0 2 0 3 1 2 1 3
2 y 3 x 1