| 题目名称 | 1567. [Ural 1520] 帝国反击战 |
|---|---|
| 输入输出 | empirestrikesback.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2014-06-19加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：14， 提交：107， 通过率：13.08% | ||||
 zhengtn03 |
100 | 0.025 s | 0.62 MiB | C++ |
 mikumikumi |
100 | 0.352 s | 0.32 MiB | C++ |
|
张灵犀不和我一般见识真可怕呢（笑 |
100 | 0.379 s | 0.32 MiB | C++ |
|
张灵犀不和我一般见识真可怕呢（笑 |
100 | 0.680 s | 0.32 MiB | C++ |
 cstdio |
100 | 0.842 s | 0.33 MiB | C++ |
|
zhengtn03 |
100 | 1.043 s | 0.40 MiB | C++ |
|
zhengtn03 |
100 | 1.392 s | 0.40 MiB | C++ |
 bobcoc |
100 | 1.498 s | 0.26 MiB | C++ |
 6666 |
100 | 1.677 s | 0.29 MiB | C++ |
|
_Itachi |
100 | 1.697 s | 0.29 MiB | C++ |
| 关于 帝国反击战 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
人生中第一次调出来搜索的参数……这是爬山算法的胜利……
| ||||
|
欧洲人爬山没有爬出AC……
| ||||
|
我一定是学了假的退火。。还是说我没有用md的“特判”？总之对着数据该参数才能90分，最后打了个表。。
_Itachi
2017-04-06 19:25
4楼
| ||||
|
我一定是学了假的退火，把srand()删了在本机就能过，否则过不了！！而且，交上去WA的点在本机能过！！Linux和Windows默认随机数表不一样！！
_Itachi
2017-04-06 14:50
3楼
| ||||
|
图是我自己加的……
造完数据才发现原题中的坐标是整数，算了不想改了，应该不影响做题…… 这道题有一个离散化方法，还有一个模拟退火+特判的方法，我用的是后者。数据刻意保证了模拟退火和特判少哪个都不行…… 与这个题类似的是POJ1379，即COGS上的“逃离陷阱”，不过精度要求稍低。 | ||||
|
@彭上铭 交的是这个题之前的版本（NOIP2005循环），我后来才把它改成这个的……
| ||||
FoolMike1567. [Ural 1520] 帝国反击战
★★★ 输入文件：empirestrikesback.in
输出文件：empirestrikesback.out
评测插件时间限制：1 s 内存限制：128 MiB
【题目描述】
贤明的乔治二世大帝统治这个繁荣且文明的帝国已经有许多年了。啊，他的国度是多么的美丽富强！在他的统治下，由钢铁和大理石建成的宏伟城市高耸入云，千里沃野遍布新苗。黄发垂髫怡然自乐，工人农民共创幸福生活……
但是乔治必须知道，可怕的危险正威胁着人类。一个愚昧而贫穷的共和国的残忍恶毒的独裁者，可怕的萨达姆三世，打算制造最新式的化学武器，并夺取对这个星球的统治。
根据一份秘密情报，萨达姆在共和国的领土内建造了N座武器工厂。共和国的领土是一个圆心为(0,0)，半径为R的圆。每座工厂都被巧妙地伪装成医院，学校或者养老院，位于笛卡尔坐标的(Xi,Yi)处。
萨达姆的邪恶意图激怒了乔治。因此他决定用炸弹摧毁所有的工厂。所有的炸弹都有同样的有效杀伤半径，并精确地落在相应的工厂上。
每一枚炸弹都能把有效杀伤半径中的一切变成一团灼热的气体。这一事实促使乔治产生了一个有趣的想法：如果能一石二鸟，把萨达姆本人也变成一团气体将会很好。不幸的是，情报部门未能确定大坏蛋萨达姆的准确行踪。因此乔治想要计算出所有炸弹的杀伤半径，使得通过精确地轰炸所有工厂就能够消灭萨达姆，无论他在共和国领土内的哪一处。顺便说一下，制造威力更大的炸弹需要许多昂贵的钋-210，因此炸弹的杀伤半径应当尽量小。
【输入格式】
输入文件的第一行有两个整数N(1<=N<=300)和R(1<=R<=1000)。
接下来的N行每行有两个实数Xi和Yi（Xi^2+Yi^2<=R^2），代表相应工厂的位置。
【输出格式】
输出一行一个实数，即所有炸弹的最小有效杀伤半径。至少输出小数点后五位。
【输入样例】
4 4
0 2
0 -2
2 0
-2 0
【输出样例】
2.94725152
【提示】
输入格式和Ural原题不同。原题中输入的坐标均为整数。当然，这里输入的实数坐标由于舍入误差有可能略微超出圆的范围，但这不影响结果。
只要你的答案和标准答案之差不超过2e-5，我们就认为你的答案是正确的。