꺾인선

아제르바이잔은 카펫으로 유명하다. 카펫 디자이너인 당신은 꺾인선을 그려 새로운 무늬를 만들려고 한다. 꺾인선은 평면 위의 $t+1$개 점 $p_0,\ldots,p_t$로 정의되는 $t$개 선분의 수열이다. 각 $0 \leq j \leq t-1$에 대해 $p_j$와 $p_{j+1}$을 잇는 선분이 있다.

평면에는 $n$개의 점이 표시되어 있고 점 $i$ ($1 \leq i \leq n$)의 좌표는 $(x[i],y[i])$이다. 어떤 두 점도 같은 $x$좌표나 같은 $y$좌표를 갖지 않는다.

다음을 모두 만족하는 점의 수열 $(sx[0],sy[0]),\ldots,(sx[k],sy[k])$을 찾아야 한다.

• $(0,0)$에서 시작한다. 즉, $sx[0]=0$, $sy[0]=0$이다.
• 모든 표시된 점을 지난다. 표시된 점이 선분의 끝점일 필요는 없다.
• 모든 선분은 수평 또는 수직이다. 즉, 연속한 두 점은 $x$좌표나 $y$좌표 중 하나가 같다.

꺾인선은 자기 자신과 교차하거나 겹칠 수 있다.

원 대회에서는 이 문제가 출력 파일 제출형 부분 점수 문제였다. Reporch에서는 공식 입력 하나를 읽고 공식 출력 형식의 꺾인선을 출력하는 C++17 프로그램을 제출한다. 공식 입력, 출력 checker, 점수 기준은 바꾸지 않았다. 올바른 꺾인선의 점수는 선분 수에 따라 정해진다.

입력 형식

• 첫째 줄: $n$
• 이어지는 $n$개 줄의 $i$번째 줄: $x[i]\;y[i]$

출력 형식

• 첫째 줄: $k$
• 이어지는 $k$개 줄의 $j$번째 줄: $sx[j]\;sy[j]$ ($1 \leq j \leq k$)

출력에는 시작점 $(sx[0],sy[0])=(0,0)$을 쓰지 않는다. 모든 좌표는 정수여야 한다.

예제

입력:

4
2 1
3 3
4 4
5 2

가능한 출력:

6
2 0
2 3
5 3
5 2
4 2
4 4

이 예제는 실제 채점 입력에는 포함되지 않는다.

제한

• $1 \leq n \leq 100\,000$
• $1 \leq x[i],y[i] \leq 10^9$
• 모든 $x[i]$, $y[i]$는 정수이다.
• $i_1 \neq i_2$이면 $x[i_1] \neq x[i_2]$이고 $y[i_1] \neq y[i_2]$이다.
• $-2\cdot10^9 \leq sx[j],sy[j] \leq 2\cdot10^9$
• 출력 크기는 $15$MB를 넘을 수 없다.

채점

각 테스트 케이스에서 최대 $10$점을 얻는다. 출력한 꺾인선이 조건을 만족하지 않으면 $0$점이다. 올바른 꺾인선이 $k$개 선분으로 이루어졌다면 테스트별 감소 수열 $c_1,\ldots,c_{10}$에 따라 다음 점수를 얻는다.

• $k=c_i$이면 $i$점
• $c_{i+1}<k<c_i$이면 $i+\frac{c_i-k}{c_i-c_{i+1}}$점
• $k>c_1$이면 $0$점
• $k<c_{10}$이면 $10$점

시각화 도구

공식 첨부 파일의 vis.py로 입력이나 출력을 시각화할 수 있다. 출력은 처음 $1000$개 선분까지만 표시된다.

python vis.py [input file]
python vis.py [input file] --solution [output file]

• 제출 프로그램은 위의 입력 형식에 따른 공식 입력 하나를 읽는다.

• 제출 프로그램은 위의 출력 형식에 따른 후보 꺾인선을 출력한다. 공식 checker가 유효성을 확인하고 부분 점수를 계산한다.