Avoiding the Abyss

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

요약
시작점, 도착점, 그리고 숨은 축 정렬 직사각형 안에 있다고 알려진 한 점이 주어질 때, 직사각형을 피하도록 경유점 10개 이하를 출력한다.
난이도

보통10점 중 5점

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

문제

You are standing on a point with integer coordinates (x_s,y_s)(x\_s, y\_s). You want to walk to the point with integer coordinates (x_t,y_t)(x\_t, y\_t). To do this, you can walk along a sequence of line segments. But there is a swimming pool in your way. The swimming pool is an axis aligned rectangle whose lower left corner is on the point (x_l,y_l)(x\_l, y\_l) and the upper right corner is on the point (x_r,y_r)(x\_r, y\_r). You cannot ever cross the swimming pool, not even on the border. However, it is dark and you do not know the coordinates (x_l,y_l)(x\_l, y\_l) and (x_r,y_r)(x\_r, y\_r). Instead, you threw a rock into the pool which revealed that the point (x_p,y_p)(x\_p, y\_p) is in the pool (or on the boundary).

Find a way to walk from the start to the end point along a sequence of line segments, so that you never cross the swimming pool.

입력

The first line contains two integers x_sx\_s and y_sy\_s (−104≤x_s,y_s≤104-10^4 \leq x\_s, y\_s \leq 10^4).

The second line contains two integers x_tx\_t and y_ty\_t (−104≤x_t,y_t≤104-10^4 \leq x\_t, y\_t \leq 10^4).

The third line contains two integers x_px\_p and y_py\_p (−104≤x_p,y_p≤104-10^4 \leq x\_p, y\_p \leq 10^4).

The problem is not adaptive, i.e. for every test case there exist four integers 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) that constitute a swimming pool. The start and end points are always strictly outside the swimming pool, and the point (x_p,y_p)(x\_p,y\_p) is inside (or on the border). The start and end points are always distinct.

출력

First, print one integer NN (0≤N≤100 \leq N \leq 10), the number of points in between the start and end point that you want to visit. Then, print NN lines, the iith containing two integers x_i,y_ix\_i, y\_i. These coordinates must satisfy −109≤x_i,y_i≤109-10^9 \leq x\_i, y\_i \leq 10^9. Note that these are not the same bounds than on the other coordinates.

This means that you will walk along straight line segments between (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) such that none of the line segments touch the swimming pool. It can be proven that a solution always exists.

예제1

  1. 예제 1

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