#2123. 田野
田野
田野
题目描述
第二试田野(fields) IOI 2019 中国国家队选拔 田野(fields) 【题目描述】 Last night I saw you running In the open fields of grace No longer were you broken or in pain1 你找到了一片一望无际的大田野,在这片田野中你忘记了曾经破碎、痛苦的过去。 你像小孩一样在上帝的恩赐中奔跑。 然而你发现了一个问题,在这片田野中有若干条峡谷。你随时都有坠入峡谷中的危 险。为了继续自由自在的奔跑,你决定用若干围栏将这些峡谷围起来。 我们可以忽视峡谷的宽度,将每一条峡谷看做一条线段。.这.些.线.段.可.以.相.交,而你 的围栏必须是.一.条.或.多.条.闭.合.不.自.交.且.两.两.不.相.交.的曲线,使得.任.何.一.个.峡.谷都.完.全 在.某.一.条闭合曲线围成的闭合区域之内。 当然,围栏需要消耗资源,消耗的资源和围栏的长度成正比,你希望最小化消耗的 资源总量,所以你希望求出围栏总长度的.下.确.界,换句话说,你希望找到一个最大的实 数x,使得不存在一个方案使得围栏总长度小于x。 【输入格式】 从文件fields.in 中读入数据。 输入文件的第一行为一个整数n,表示峡谷的个数。 接下来n 行,第i 行四个整数ai, bi, ci, di,表示第i 条峡谷为一条连接点(ai, bi) 和 点(ci, di) 的线段。.保.证.两.个.端.点.不.重.合,.不.同.的.线.段.不.会.涉.及.到.相.同.的.点。.保.证.任.意 .三.点.不.共.线。 【输出格式】 输出到文件fields.out 中。 输出一行一个实数,表示围栏总长度的下确界。.你.的.答.案.和.标.准.答.案.的.绝.对.误.差.和 .相.对.误.差.的.最.小.值.不.能.超.过10−6。 【样例1 输入】 1 0 0 0 1 1题面中的歌词来自Jackie Evancho 的Open Fields of Grace,作曲者为Lisa Venkatrathnam 和Paul Sumares。 第2 页 共9 页 第二试田野(fields) IOI 2019 中国国家队选拔 【样例1 输出】 2.00000000 【样例1 解释】 一个四个端点分别为(−0.01, −0.01), (−0.01, 1.01), (0.01, 1.01), (0.01, −0.01) 的长方形 完全包含输入的线段,且总长度为2.08,略大于下确界。 我们可以证明,不存在长度恰好为2 的方案。我们可以通过将正方形无限向输入 线段“缩紧”来构造一个长度为任意大于2 的方案。 【样例2 输入】 4 -1 7 0 7 0 0 0 1 2 -3 5 5 2 2 6 -1 【样例2 输出】 23.563573998194637061425470524757 【样例2 解释】 下图为输入的线段,注意线段可以相交: 第3 页 共9 页 第二试田野(fields) IOI 2019 中国国家队选拔 图1: 样例2 解释 我们可以通过无限“逼近”这些红色的曲线来构造任意总长度大于答案的方案。注 意通过样例1,我们很容易知道左上角的红色线段被算了两遍。 【样例3 输入】 4 -1 1 -1 3 0 4 2 4 3 1 3 3 0 0 2 0 【样例3 输出】 13.656854249492380195206754896839 【样例3 解释】 √ 答案为8 + 4 2。 解释如图: 第4 页 共9 页 第二试田野(fields) IOI 2019 中国国家队选拔 图2: 样例3 解释 √ 我们可以通过无限“逼近”这些红色的曲线来构造任意总长度大于8 + 4 2 的 方案。 【样例4】 见选手目录下的fields/fields4.in 与fields/fields4.ans。 【测试数据约定】 对于5% 的数据,保证1 ≤n ≤1。 对于10% 的数据,保证1 ≤n ≤2。 对于15% 的数据,保证1 ≤n ≤10。 对于30% 的数据,保证1 ≤n ≤15。 对于45% 的数据,保证1 ≤n ≤30。 对于55% 的数据,保证1 ≤n ≤60。 对于65% 的数据,保证1 ≤n ≤120。 对于75% 的数据,保证1 ≤n ≤200。 对于另外10% 的数据,保证答案最多包含两条曲线。 对于100% 的数据,保证1 ≤n ≤250,0 ≤|ai|, |bi|, |ci|, |di| ≤109。.保.证.两.个.端.点.不.重 .合,.不.同.的.线.段.不.会.涉.及.到.相.同.的.点。.保.证.任.意.三.点.不.共.线。 第5 页 共9 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
1
0 0 0 1
2.00000000
样例 2
4
-1 7 0 7
0 0 0 1
2 -3 5 5
2 2 6 -1
23.563573998194637061425470524757