만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

수영장 피하기

시간 제한1초메모리 제한1024 MB

요약
알려지지 않은 축 정렬 직사각형이 주어진 점을 포함한다고 할 때, 시작점에서 도착점까지 직사각형에 닿지 않는 경유점을 최대 10개 찾습니다.
난이도

보통10점 중 6점

유형
기하, 구현
정답자
아직 제출이 없습니다

문제

현재 정수 좌표 (x_s,y_s)(x\_s, y\_s)인 점에 서 있다. 정수 좌표 (x_t,y_t)(x\_t, y\_t)인 점까지 걸어가려고 한다. 선분들을 차례로 따라 걸어서 도착할 수 있다. 가는 길에 수영장이 있다. 수영장은 축에 평행한 직사각형이며, 왼쪽 아래 꼭짓점이 (x_l,y_l)(x\_l, y\_l), 오른쪽 위 꼭짓점이 (x_r,y_r)(x\_r, y\_r)에 있다. 경계 위라도 수영장을 가로지를 수 없다.

다만 주변이 어두워서 (x_l,y_l)(x\_l, y\_l)과 (x_r,y_r)(x\_r, y\_r)는 알 수 없다. 돌을 던져 보았더니 점 (x_p,y_p)(x\_p, y\_p)가 수영장 안이나 경계 위에 있다는 것을 알았다.

시작점에서 도착점까지, 수영장을 가로지르지 않는 선분들을 따라 걷는 방법을 찾아라.

입력

첫째 줄에 정수 x_sx\_s, y_sy\_s가 주어진다 (−104≤x_s,y_s≤104-10^4 \leq x\_s, y\_s \leq 10^4).

둘째 줄에 정수 x_tx\_t, y_ty\_t가 주어진다 (−104≤x_t,y_t≤104-10^4 \leq x\_t, y\_t \leq 10^4).

셋째 줄에 정수 x_px\_p, y_py\_p가 주어진다 (−104≤x_p,y_p≤104-10^4 \leq x\_p, y\_p \leq 10^4).

이 문제는 적응형이 아니다. 모든 테스트 케이스에 대해 수영장을 이루는 정수 x_l,y_l,x_r,y_rx\_l, y\_l, x\_r, y\_r (−104≤x_l<x_r≤104-10^4 \leq x\_l < x\_r \leq 10^4, −104≤y_l<y_r≤104-10^4 \leq y\_l < y\_r \leq 10^4)이 정해져 있다. 시작점과 도착점은 항상 수영장 바깥에 있고 서로 다르다. 점 (x_p,y_p)(x\_p, y\_p)는 수영장 안이나 경계 위에 있다.

출력

먼저 시작점과 도착점 사이에서 방문할 점의 개수 NN (0≤N≤100 \leq N \leq 10)을 출력한다. 이어서 NN개의 줄에 ii번째 점의 정수 좌표 x_i,y_ix\_i, y\_i를 출력한다. 이 좌표는 −109≤x_i,y_i≤109-10^9 \leq x\_i, y\_i \leq 10^9를 만족해야 한다. 다른 좌표의 범위와 다르다는 점에 유의한다.

이동은 (x_s,y_s),(x_1,y_1),…,(x_N,y_N),(x_t,y_t)(x\_s, y\_s), (x\_1, y\_1), \dots, (x\_N, y\_N), (x\_t, y\_t)를 차례로 잇는 직선 선분을 따른다. 어느 선분도 수영장에 닿아서는 안 된다. 해가 항상 존재함을 증명할 수 있다.

예제1

  1. 예제 1

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