#P1050. 星战
星战
题目背景
这次可以了,总司令。
题目描述
在这一轮的星际战争中,敌方在宇宙中建立了 个据点,第 个据点位于坐标 。第 个据点有一个脆弱值,记为 。
你作为联合舰队的参谋长正在策划一次攻击。你将选择宇宙中一个坐标 ,放置一枚反物质炸弹。
反物质炸弹有一个威力参数 。如果要炸毁第 个据点,那么就要求威力参数和据点 的脆弱值乘积大于等于它们之间的曼哈顿距离,也就是说威力参数至少是
注意到上式不一定是整数。炸弹的参数也不必要是整数。同时,炸弹的坐标也不必要是整数。
你希望炸弹可以炸毁全部的 个据点。同时,威力参数越大,炸弹造价越高。因此你希望选择一个合适的坐标来放下炸弹,使得炸弹可以炸毁所有的据点,且炸弹的威力参数尽可能小。
据点的坐标可以重合,炸弹的坐标也可以与据点相同。
输入格式
第一行是一个整数,表示敌方据点数量 。
接下来 行,每行四个非负整数 ,描述一个敌方据点。
输出格式
输出一行一个实数,表示最小的符合要求的威力参数。
当你的输出与答案的绝对或相对误差不超过 时被认为正确。
样例
样例输入 1
4
0 0 0 1
1 2 0 1
3 4 0 1
2 1 0 1
样例输出 1
3.50000000
样例输入 / 输出 2
见下发文件 galaxy2.in/ans
。该样例满足测试点 的限制。
样例输入 / 输出 3
见下发文件 galaxy3.in/ans
。该样例满足测试点 的限制。
数据范围与提示
本题共 个测试点,每个测试点 分。
测试点编号 | 特殊性质 |
---|---|
所有 相同 | |
且坐标不超过 | |
对于所有数据,,,。