#P16931. [SGU315]The Highway Belt
[SGU315]The Highway Belt
SGU 315 The Highway Belt
题目描述
Berland 决定修建一条环绕首都的高速公路。
国王 Berbinduk IX 希望这条高速公路是一条闭合折线,并且关于首都呈“星形”。也就是说,从首都出发的任意一条射线,都必须与高速公路恰好相交于一个点。
为了节省时间和建设成本,国王决定只利用已有道路修建高速公路。更准确地说,高速公路的各条线段必须由已有道路或已有道路的一部分组成。
你是 Berland 第一国家道路建设公司的负责人,并获得了修建这条高速公路的合同。修建的高速公路越长,你能够获得的收益就越高。
因此,你需要在满足国王上述所有要求的前提下,修建一条总长度尽可能大的高速公路。
输入格式
第一行包含一个整数 ,表示已有道路的数量。
。
接下来 行,每行包含四个整数 ,表示一条已有道路的两个端点分别为 和 。
所有坐标的绝对值均不超过 。
道路允许长度为 。
首都位于坐标原点 。
输出格式
输出能够修建出的高速公路的最大长度,要求小数点后至少具有 位精度。
如果无法修建出正长度的合法高速公路,输出 0。
样例 1
6
2 2 2 -2
-2 2 -2 -2
2 2 -2 2
-2 -2 2 -2
3 0 -1 4
-2 1 0 3
16.82843
样例 2
1
1 1 -1 -1
0