수영장 피하기
시간 제한1초메모리 제한1024 MB
알려지지 않은 축 정렬 직사각형이 주어진 점을 포함한다고 할 때, 시작점에서 도착점까지 직사각형에 닿지 않는 경유점을 최대 10개 찾습니다.
문제
현재 정수 좌표 인 점에 서 있다. 정수 좌표 인 점까지 걸어가려고 한다. 선분들을 차례로 따라 걸어서 도착할 수 있다. 가는 길에 수영장이 있다. 수영장은 축에 평행한 직사각형이며, 왼쪽 아래 꼭짓점이 , 오른쪽 위 꼭짓점이 에 있다. 경계 위라도 수영장을 가로지를 수 없다.
다만 주변이 어두워서 과 는 알 수 없다. 돌을 던져 보았더니 점 가 수영장 안이나 경계 위에 있다는 것을 알았다.
시작점에서 도착점까지, 수영장을 가로지르지 않는 선분들을 따라 걷는 방법을 찾아라.
입력
첫째 줄에 정수 , 가 주어진다 ().
둘째 줄에 정수 , 가 주어진다 ().
셋째 줄에 정수 , 가 주어진다 ().
이 문제는 적응형이 아니다. 모든 테스트 케이스에 대해 수영장을 이루는 정수 (, )이 정해져 있다. 시작점과 도착점은 항상 수영장 바깥에 있고 서로 다르다. 점 는 수영장 안이나 경계 위에 있다.
출력
먼저 시작점과 도착점 사이에서 방문할 점의 개수 ()을 출력한다. 이어서 개의 줄에 번째 점의 정수 좌표 를 출력한다. 이 좌표는 를 만족해야 한다. 다른 좌표의 범위와 다르다는 점에 유의한다.
이동은 를 차례로 잇는 직선 선분을 따른다. 어느 선분도 수영장에 닿아서는 안 된다. 해가 항상 존재함을 증명할 수 있다.