P7449 [THUSC 2016] 星露谷物语

最近，小葱为了忘记城市的喧嚣，来到了星露谷开始种地发家致富。但是，由于小葱把钱都拿去抽卡了，所以小葱并没有足够的钱来买种子。为了搜集足够的钱来养猪，小葱必须开始大规模的搜寻野菜工作。 星露谷是一个无限大的二维平面，你可以在这个二维平面内任意移动。小葱可能在星露谷的 $n$ 条线段上找到野菜，但是这些线段是有向的，小葱必须沿着线段的方向移动才能找到野菜。为了找到更多的野菜，小葱希望自己能把星露谷中所有可能出现野菜的地方全部走一遍。换句话说，对于每条线段，小葱都需要沿着该线段的方向将这条线段的每个点都经过一遍。当然，小葱可以选择分多次走一条线段，具体地讲，小葱可以在这条线段的任意位置离开这条线段，再从任意位置进入这条线段，只要保证路径的并集覆盖了这条有向线段即可。 小葱希望找到一条尽量短的路径，这条路径应该由 $m$ 条线段组成，并且覆盖了星露谷中的 $n$ 条有向线段。小葱可以选择星露谷的任意一个点作为路径的起点，同时它也必须是路径的终点，即小葱最终必须回到出发的位置。 现在，小葱要去写四子棋大作业了，他不知道该怎么规划自己的行走方案使得自己移动的距离尽量短，所以就把这个艰巨的任务交给聪明的你了。 **注意：如果有两条线段的某部分重合且方向相同，那么你在走过这一段的时候我们认为这两条线段的这部分都被走过了。**

第一行包含一个整数 $n$，代表图中有向线段的数量。 接下来 $n$ 行，每行四个整数 $x_1,y_1,x_2,y_2$，代表这条线段是一条从 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的有向线段。

第一行应包含一个整数 $m$，代表小葱所走的折线路径中点的数量，需要满足 $m\le\min(5n^2,5\times 10^6)$。 接下来 $m$ 行，按照路径的顺序依次输出路径上的点。每行应包含两个浮点数 $x,y$，用来描述一个点的横、纵坐标。其中，$x,y$ 请保留不超过 $5$ 位小数。

**本题为提交答案题，输入与 checker 将会在附件给出** 对于每组测试数据，如果你的输出格式不符合题目要求，或者你输出的路径并没有走完给定的条 $n$ 有向线段，那么该测试点得 $0$ 分。否则，我们会计算你给出路径的长度 $d$，并根据 $10$ 个评分参数 $a_1\ge a_2\ge...\ge a_{10}$ 计算你的得分： $$\max\{i|d\le a_i,1\le i\le 10\}$$ 数据保证 $a_1$ 足够大，以确保一个合法的方案至少可以得到 $1$ 分。 #### 样例解释 对于样例 $1$，小葱总共移动了 $200+100\sqrt2$ 的距离，这也是这组样例的最优解。 对于样例 $2$，在该组解中，小葱一共移动了 $202+\sqrt{2402}+\sqrt{2602}$ 的距离，但这并不是这组数据的最优解。