{"problem":{"name":"[COCI 2022/2023 #1] Berilij","description":{"content":"就在 COCI 比赛当天，外星人计划乘 $n$ 艘宇宙飞船访问地球，授予参赛者丰厚的奖励。他们的宇宙飞船都是完美的圆形。 出于安全考虑，他们选择了 $m$ 对在着陆时外部必须相接触的飞船。外星人已经确定了每艘飞船的着陆点坐标，而 Berilij 的任务是确定每艘飞船的半径，以确保所有飞船都能安全着陆。 ![](https://cdn.luogu.com.cn/upload/image_host","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9030"},"statements":[{"statement_type":"Markdown","content":"就在 COCI 比赛当天，外星人计划乘 $n$ 艘宇宙飞船访问地球，授予参赛者丰厚的奖励。他们的宇宙飞船都是完美的圆形。\n\n出于安全考虑，他们选择了 $m$ 对在着陆时外部必须相接触的飞船。外星人已经确定了每艘飞船的着陆点坐标，而 Berilij 的任务是确定每艘飞船的半径，以确保所有飞船都能安全着陆。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/frerrx7n.png)\n\n如图，左右两对飞船均不满足外部接触的条件。只有中间的一对飞船满足外部接触的条件。换句话说，“外部接触”定义为当且仅当两艘飞船对应的圆形**外切**时，这两艘飞船的外部相接触。\n\n宇宙飞船造价昂贵，它们的成本等于它们的面积，所以外星人希望宇宙飞船成本尽可能小。由于外星人科技非常先进，因此外星人的宇宙飞船可以重叠，直径也可以为 $0$。\n\n如果 Berilij 不能解决这个问题，外星人将会吃掉她！请你帮帮小羊 Berilij。\n\n## Input\n\n第一行包含两个整数 $n,m$，分别表示外星人的飞船数量以及需要接触的飞船的对数。\n\n接下来 $n$ 行每行两个实数 $x_i,y_i$，表示第 $i$ 艘飞船着陆点的坐标。给出的坐标均精确到小数点后十位。\n\n下面的 $m$ 行包含两个整数 $a_i$ 和 $b_i$，表示第 $a_i$ 号和第 $b_i$ 号飞船在着陆后必须外部接触。数据保证无序对 $(a_i,b_i)$ 不重复。\n\n## Output\n\n如果无解，输出一行```NE```。\n\n否则第一行输出```DA```，接下来 $n$ 行输出成本最小的方案下每艘飞船的半径。\n\n[samples]\n\n## Background\n\n小羊 Berilij 被外星人绑架了。她需要帮助外星人解决一个问题。\n\n## Note\n\n当你的答案与正确答案误差不大于 $10^{-4}$ 时，答案被视为正确的。\n\n| 子任务 | 分值 | 特殊性质 |\n| :----------: | :----------: | :----------: |\n| $1$ | $15$ | $n$ 为奇数且所有飞船都恰好与两艘飞船接触 |\n| $2$ | $25$ | 数据保证有解 |\n| $3$ | $30$ | 对于任何一对飞船 $(a,b)$ 都有且仅有一个飞船序列满足其起始于 $a$ 结束于 $b$ 且此序列内任意相邻的两艘飞船都彼此接触 |\n| $4$ | $40$ | 无特殊性质 |\n\n对于 $100\\%$ 的数据，$1\\leq n,m \\leq 10^5,-10^4\\leq x_i,y_i \\leq 10^4,1\\leq a_i,b_i \\leq n$ 且 $a_i \\neq b_i$。\n\n本题满分 $110$ 分。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9030","tags":["2022","Special Judge","COCI（克罗地亚）"],"sample_group":[["3 3\n0.0000000000 0.0000000000\n0.0000000000 2.0000000000\n2.0000000000 0.0000000000\n1 2\n2 3\n3 1","DA\n0.585786\n1.414214\n1.414214"],["5 4\n-0.4585133080 0.2893567973\n9.9368007273 7.1806641913\n-8.4621834970 -2.8309311865\n0.0122121945 -2.8309311865\n2.3991780589 -8.8626906628\n2 1\n3 2\n4 3\n5 1","DA\n0.000000\n12.472076\n8.474396\n0.000000\n9.587824"],["5 5\n0.0000000000 0.0000000000\n1.0000000000 2.0000000000\n2.0000000000 4.0000000000\n3.0000000000 6.0000000000\n4.0000000000 8.0000000000\n1 2\n2 3\n3 4\n4 5\n5 1","NE"]],"created_at":"2026-03-03 11:09:25"}}