왕국 분할
시간 제한2초메모리 제한512 MB
평면 위의 서로 다른 n개의 반정수 좌표 점들이 주어질 때, 어떤 두 점도 같은 영역에 남지 않도록 정수 좌표의 축 평행 직선을 n-1개 이하로 출력한다.
문제
플랫랜드 왕국은 무한한 2차원 평면이다. 왕국에는 개의 성이 있다. 지도를 더 편하게 그리기 위해 플랫랜드에는 데카르트 좌표계가 도입되었다. 번째 성은 좌표가 인 점에 있고, 여기서 , 는 정수이다. 모든 성의 위치는 서로 다르다.
나이가 든 왕은 지도 위에서 왕국을 아들들에게 좌표축에 평행한 직선으로 나누기로 했다. 직선이 축에 평행하면 그 직선 위 모든 점의 좌표가 정수여야 하고, 그렇지 않으면 모든 점의 좌표가 정수여야 한다. 두 경우 모두 해당 정수 좌표의 절댓값은 를 넘지 않아야 한다. 왕은 왕국을 나눈 뒤 어떤 두 성도 서로 다른 부분에 있기를 원한다.
왕이 개 이하의 직선으로 왕국을 나누도록 도와라. 어떤 두 직선도 공통점을 하나 이하로 가져야 한다.
입력
첫째 줄에 정수 ()이 주어진다. 이는 왕국에 있는 성의 수이다. 다음 개 줄에 두 수 와 (, )가 주어진다. 이는 성 좌표의 정수 부분이다.
출력
첫째 줄에 사용하는 직선의 수를 출력한다. 다음 줄들에 직선을 한 줄에 하나씩 출력한다. 직선이 축에 평행하면 문자 y를 출력하고 그다음에 공백을 두고 그 직선 위 모든 점의 좌표를 출력한다. 그렇지 않으면 문자 x를 출력하고 그다음에 공백을 두고 그 직선 위 모든 점의 좌표를 출력한다.
힌트
