#23901. 臼邦外卖员问题

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: root

题目描述

遥想 2021 级问题求解(三)期末理论测试时,Bardisk 对图论志在必得,用五分钟切了某作业原题后,将目光投向第二题。在看完第二题题目的一瞬间,他此前还在挥斥方遒的手僵硬了。

「请写出中国邮递员问题的定义。」

「淦,旅行商问题听过,邮递员问题是什么鬼?」

正当 Bardisk 后悔不该从不出席理论课时,马老师的声音传来:

「大家想一想邮递员的任务是什么?」

Bardisk 恍然大悟,体会到了马老师的良苦用心:

「没错,邮递员的任务是送信啊!一定是要访问每个点至少一次!」

*以下省去不堪回忆若干*

考完考试,Bardisk 沾沾自喜,用某 IM 软件向 Barisore 吹捧了一番自己的机智。然而 Barisore 早就考过了《离散数学》,不屑地甩出了维基百科上中国邮递员问题的定义,然后揶揄道:

「得了吧,送件上门,你以为是外卖员啊!」

以下是题目正文。

「凭什么谁都可以随便定义一个问题还要别人都知道啊kora!」

抱着这样的叛逆想法,Bardisk 决定定义一个「臼邦外卖员问题」来造(恶)福(心)后人,这个问题的设定是这样的:

某外卖员需要从城市出发给一条河沿岸的 个村庄送外卖,然后再返回城市。而由于连日高温天气,外卖员在从一地前往另一地的途中都需要去河边装一次水。请你根据城市、村庄、河流的位置为外卖员规划一条最短的送外卖路径。

形式化地,村庄和城市等居民点可抽象为二维平面上的几何定点,外卖员是一个几何动点,河流则是一条几何定直线。外卖员将从城市所在点出发,依次访问 号村庄所在点,然后返回城市所在点。特别地,外卖员每次从一个点前往一个点的轨迹都必须和河流所在直线至少有一个交点。可以证明,外卖员的最短轨迹是一条折线,而我们需要你给出这条最短折线的总长度、折点个数(除居民点)、以及按访问顺序的这些折点的坐标。

输入格式

第一行一个正整数 ,含义如题。

接下来 行,第 行两个数 ,表示村庄在以城市为原点的二维直角坐标系上的位置。

最后一行三个数 ,表示河流在以城市为原点的二维直角坐标系上的一般式方程 (保证直线合法)。

输出格式

第一行一个数,表示路径最短长度。

第二行一个数,表示除居民点外的折点个数 。

接下来 行,第 行两个数 ,表示第 个上述折点的坐标,以单空格分隔。

你的所有输出和标准答案的误差不应超过 。

样例

样例输入 1

1
1 0
0 1 -1

样例输出 1

4.472136
2
0.500000 1.000000
0.500000 1.000000

样例输入 2

1
1919 810
11 45 14 

样例输出 2

4166.611751
2
0.323041 -0.390077
0.323041 -0.390077

样例输入 3

2
3 -8
4 3
0 1 5

样例输出 3

33.190835
1
1.538462 -5.000000

数据范围与提示

对于前 的数据,。(提示:河流与 轴平行)。

对于前 的数据,。

另有 的数据,保证每次外卖员出发的目的地都在河流另一侧(提示:此时 )。

对于所有数据,,其余出现的所有数绝对值不超过 。

保证所有居民点不在河流上。