시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 12 | 10 | 10 | 83.333% |
Королевство Флатландия имеет вид бесконечной двумерной плоскости. В королевстве находится $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 x 1 y 3