아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

왕국 분할

시간 제한2초메모리 제한512 MB

요약
평면 위의 서로 다른 n개의 반정수 좌표 점들이 주어질 때, 어떤 두 점도 같은 영역에 남지 않도록 정수 좌표의 축 평행 직선을 n-1개 이하로 출력한다.
난이도

보통10점 중 7점

유형
분할 정복, 기하, 정렬, 재귀
정답자
아직 제출이 없습니다

문제

플랫랜드 왕국은 무한한 2차원 평면이다. 왕국에는 nn개의 성이 있다. 지도를 더 편하게 그리기 위해 플랫랜드에는 데카르트 좌표계가 도입되었다. ii번째 성은 좌표가 (xi+0.5,yi+0.5)(x_i+0.5, y_i+0.5)인 점에 있고, 여기서 xix_i, yiy_i는 정수이다. 모든 성의 위치는 서로 다르다.

나이가 든 왕은 지도 위에서 왕국을 아들들에게 좌표축에 평행한 직선으로 나누기로 했다. 직선이 OxOx축에 평행하면 그 직선 위 모든 점의 yy좌표가 정수여야 하고, 그렇지 않으면 모든 점의 xx좌표가 정수여야 한다. 두 경우 모두 해당 정수 좌표의 절댓값은 2⋅1092 \cdot 10^9를 넘지 않아야 한다. 왕은 왕국을 나눈 뒤 어떤 두 성도 서로 다른 부분에 있기를 원한다.

왕이 n−1n-1개 이하의 직선으로 왕국을 나누도록 도와라. 어떤 두 직선도 공통점을 하나 이하로 가져야 한다.

입력

첫째 줄에 정수 nn (1≤n≤100 0001 \le n \le 100\,000)이 주어진다. 이는 왕국에 있는 성의 수이다. 다음 nn개 줄에 두 수 xix_i와 yiy_i (−109≤xi≤109-10^9 \le x_i \le 10^9, −109≤yi≤109-10^9 \le y_i \le 10^9)가 주어진다. 이는 성 좌표의 정수 부분이다.

출력

첫째 줄에 사용하는 직선의 수를 출력한다. 다음 줄들에 직선을 한 줄에 하나씩 출력한다. 직선이 OxOx축에 평행하면 문자 y를 출력하고 그다음에 공백을 두고 그 직선 위 모든 점의 yy좌표를 출력한다. 그렇지 않으면 문자 x를 출력하고 그다음에 공백을 두고 그 직선 위 모든 점의 xx좌표를 출력한다.

힌트

예제1

  1. 예제 1

    입력
    4
    0 2
    0 3
    1 2
    1 3
    
    예상 출력
    2
    x 1
    y 3