找边界

找边界

问题描述
一些闭合的折线(这些折线可能相交)将平面分成一些区域。区中有一个区域是没有边界的——就是折线的外部区域。所有的边界的区域和折线本身构成了内部区域(图中的阴影部分)。每部区域的边界也是一个折线(图中的粗线)。你的任务就是找到给定折线的边界。
在确立了起始点以后,为了保证解的唯一性。我要求输出满足:
*不会出现两条线段(有公共的端点除外)
*相邻的两个节点不重合
*相临的两条边不在同一至线上。
*当你沿着边界前进时,内部区域总是在你左边
*起始点为横坐标最小的点,若这样的点不止一个,则选其中纵坐标最小的点
样例图:https://pan.baidu.com/s/1CNW0mvhZKYwfd6ZRb1fx4g
输入格式
输入文件的第一行包含一个整数n(3≤n≤100)——在原折线的节点数。以下的n行。每行有两个整数xi,yi(0≤xi,yi≤100),表示该点的坐标。所有点都是不同的并且没有三点共线的情况。所有的相临边不在同一条直线上。
输出格式
输出文件第一行是整数m——边界上的点数。以下的m行都是点的坐标。所有的坐标精确到小数点后4位。
输入样例
10
4 9
9 9
12 4
10 2
9 5
14 10
14 5
10 9
11 4
4 4
输出样例
13
4.0000 4.0000
9.3333 4.0000
10.0000 2.0000
12.0000 4.0000
10.5000 6.5000
11.5000 7.5000
14.0000 5.0000
14.0000 10.0000
11.5000 7.5000
10.0000 9.0000
10.5000 6.5000
9.0000 9.0000
4.0000 9.0000