登山

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

有两个人站在一山脉的两头,处在同一水平位置。该山脉可以用如图1所示的二维图来表示。他们尝试用一种特别的形式登上该山脉的顶峰。他们约定要保证任何时刻都处在同一水平位置。现在想请你来写一个程序为他们制定行走路线,尽量使路线的步数少。这里的步数不是现实中一般的概念,一步是指他们沿着向上(或向下)方向走的一段路。他们每转一次方向(由向上变为向下或由下变为向上),则步数加一步。 

 

Input

输入数据的第一行只有一个整数n(n<=30)。接着有n+1行坐标,每行有两个整数,分别为x,y坐标。每个坐标代表山脉上的一个山峰或山谷。我们用(Xi,Yi)表示第i个坐标,i=1,...,n+1。 

输入数据满足X1 < X2 <  ... < Xn+1,Y1=Yn+1 < min(Y2,Y3,...,Yn)。而且存在一个山峰(Xj,Yj),1 < j>max(Y1,...,Yj-1,Yj+1,...,Yn+1)。

Output

所求得的最少步数路线用一坐标序列来表示。输出数据第一行是一个整数m,表示坐标序列的转折点总数。接下的m行依次为m个行走路线中的转折点(转上下方向的点,包括起点和终点)。每个转折点用两个坐标表示,第一个坐标表示第一个人(开始时在(X1,Y1)的位置,第二个坐标表示第二个人(开始时在(Xn+1,Yn+1)的位置。坐标要求保留两位小数,四个数之间用一个空格分开。

Sample Input

6
0 0
2 2
3 1
7 5
11 1
13 3
16 0

Sample Output

6
0.00 0.00 16.00 0.00
2.00 2.00 14.00 2.00
3.00 1.00 15.00 1.00
5.00 3.00 13.00 3.00
3.00 1.00 11.00 1.00
7.00 5.00 7.00 5.00

Hint

Source