{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\n\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n \u003ch1\u003e\u003cfont color\u003d\"#000\"\u003e问题 C: \u003c/font\u003e \u003c/h1\u003e\n \u003cp\u003e尼古拉斯·Y·阿尔福德是一个猫奴。他在一个村庄里有一个花园,养了很多猫。这些猫太可爱了,村里的人们也都喜欢它们。\u003c/p\u003e\n \u003cp\u003e一天,一个邪恶的女巫来到了村庄。她嫉妒这些被人们喜爱的猫。她在花园里驱动了一些魔法桩,并用魔法栅栏将猫困在其中。她说:“你的猫们将被关在栅栏里,直到它们变成丑陋的老猫。”就像是一个诅咒,然后离开了。\u003c/p\u003e\n \u003cp\u003e尼古拉斯试图用锤子打破栅栏,但是栅栏对他的努力来说是坚不可摧的。他去了一座教堂,请求一位牧师的帮助。牧师在书中寻找如何摧毁魔法栅栏的方法,发现可以用圣水来摧毁它们。摧毁一段栅栏所需的圣水量与栅栏的长度成正比。然而,圣水非常昂贵。所以他决定购买恰好足够拯救所有猫的最小量的圣水。需要多少圣水呢?\u003c/p\u003e\n \u003ch2\u003e输入\u003c/h2\u003e\n \u003cp\u003e输入的格式如下:\u003c/p\u003e\n \u003cp\u003e\u003ci\u003eN M\u003c/i\u003e\u003cbr\u003e\u003ci\u003ex\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e \u003ci\u003ey\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e\u003cbr\u003e\n .\u003cbr\u003e\n .\u003cbr\u003e\n .\u003cbr\u003e\u003ci\u003ex\u003c/i\u003e\u003csub\u003e\u003ci\u003eN\u003c/i\u003e\u003c/sub\u003e \u003ci\u003ey\u003c/i\u003e\u003csub\u003e\u003ci\u003eN\u003c/i\u003e\u003c/sub\u003e\u003cbr\u003e\u003ci\u003ep\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e \u003ci\u003eq\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e\u003cbr\u003e\n .\u003cbr\u003e\n .\u003cbr\u003e\n .\u003cbr\u003e\u003ci\u003ep\u003c/i\u003e\u003csub\u003e\u003ci\u003eM\u003c/i\u003e\u003c/sub\u003e \u003ci\u003eq\u003c/i\u003e\u003csub\u003e\u003ci\u003eM\u003c/i\u003e\u003c/sub\u003e\u003cbr\u003e\u003c/p\u003e\n \u003cp\u003e输入的第一行包含两个整数 \u003ci\u003eN\u003c/i\u003e (2 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 10000) 和 \u003ci\u003eM\u003c/i\u003e (1 ≤ \u003ci\u003eM\u003c/i\u003e)。 \u003ci\u003eN\u003c/i\u003e 表示魔法桩的数量,\u003ci\u003eM\u003c/i\u003e 表示魔法栅栏的数量。接下来的 \u003ci\u003eN\u003c/i\u003e 行描述了魔法桩的坐标。每行包含两个整数 \u003ci\u003ex\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e 和 \u003ci\u003ey\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e (-10000 ≤ \u003ci\u003ex\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003ey\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e ≤ 10000)。接下来的 \u003ci\u003eM\u003c/i\u003e 行描述了魔法栅栏的两个端点。每行包含两个整数 \u003ci\u003ep\u003csub\u003ej\u003c/sub\u003e\u003c/i\u003e 和 \u003ci\u003eq\u003csub\u003ej\u003c/sub\u003e\u003c/i\u003e (1 ≤ \u003ci\u003ep\u003csub\u003ej\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003eq\u003csub\u003ej\u003c/sub\u003e\u003c/i\u003e ≤ \u003ci\u003eN\u003c/i\u003e)。它表示一段栅栏从第 \u003ci\u003ep\u003csub\u003ej\u003c/sub\u003e\u003c/i\u003e 个桩到第 \u003ci\u003eq\u003csub\u003ej\u003c/sub\u003e\u003c/i\u003e 个桩。\u003c/p\u003e\n \u003cp\u003e你可以假设以下条件成立:\u003c/p\u003e\n \u003cul\u003e\n \u003cli\u003e没有两个桩具有相同的坐标。\u003c/li\u003e\n \u003cli\u003e桩不会位于栅栏的中间。\u003c/li\u003e\n \u003cli\u003e没有两段栅栏会相交。\u003c/li\u003e\n \u003cli\u003e每个封闭区域至少有一只猫。\u003c/li\u003e\n \u003cli\u003e无法部分摧毁一段栅栏。\u003c/li\u003e\n \u003cli\u003e摧毁一段魔法栅栏需要一单位的圣水。\u003c/li\u003e\n \u003c/ul\u003e\n \u003ch2\u003e输出\u003c/h2\u003e\n \u003cp\u003e输出一行,包含拯救所有猫所需的最小量的圣水。你的程序可以在小数点后输出任意数量的数字。然而,绝对误差应该小于等于0.001。\u003c/p\u003e\n \u003ch2\u003e样例输入 1\u003c/h2\u003e\n \u003cpre\u003e3 3\n0 0\n3 0\n0 4\n1 2\n2 3\n3 1\n\u003c/pre\u003e\n \u003ch2\u003e样例输出 1\u003c/h2\u003e\n \u003cpre\u003e3.000\n\u003c/pre\u003e\n \u003ch2\u003e样例输入 2\u003c/h2\u003e\n \u003cpre\u003e4 3\n0 0\n-100 0\n100 0\n0 100\n1 2\n1 3\n1 4\n\u003c/pre\u003e\n \u003ch2\u003e样例输出 2\u003c/h2\u003e\n \u003cpre\u003e0.000\n\u003c/pre\u003e\n \u003ch2\u003e样例输入 3\u003c/h2\u003e\n \u003cpre\u003e6 7\n2 0\n6 0\n8 2\n6 3\n0 5\n1 7\n1 2\n2 3\n3 4\n4 1\n5 1\n5 4\n5 6\n\u003c/pre\u003e\n \u003ch2\u003e样例输出 3\u003c/h2\u003e\n \u003cpre\u003e7.236\n\u003c/pre\u003e\n \u003ch2\u003e样例输入 4\u003c/h2\u003e\n \u003cpre\u003e6 6\n0 0\n0 1\n1 0\n30 0\n0 40\n30 40\n1 2\n2 3\n3 1\n4 5\n5 6\n6 4\n\u003c/pre\u003e\n \u003ch2\u003e样例输出 4\u003c/h2\u003e\n \u003cpre\u003e31.000\n\u003c/pre\u003e\n \u003c/body\u003e\n\u003c/html\u003e"}}]}