Gym101981D - 2018ACM-ICPC南京现场赛D题 Country Meow
2018ACM-ICPC南京现场赛D题-Country Meow
Problem D. Country Meow
Input file: standard input
Output file: standard output
In the 24th century, there is a country somewhere in the universe, namely Country Meow. Due to advanced technology, people can easily travel in the 3-dimensional space.
There are N cities in Country Meow. The i-th city is located at (xi, yi, zi) in Cartesian coordinate.
Due to the increasing threat from Country Woof, the president decided to build a new combatant command, so that troops in different cities can easily communicate. Hence, the Euclidean distance between the combatant command and any city should be minimized.
Your task is to calculate the minimum Euclidean distance between the combatant command and the farthest city.
Input
The first line contains an integer N (1 ≤ N ≤ 100).
The following N lines describe the i-th city located.Each line contains three integers xi, yi, zi(−100000 ≤ xi, yi, zi ≤ 100000).
Output
Print a real number — the minimum Euclidean distance between the combatant command and the farthest city. Your answer is considered correct if its absolute or relative error does not exceed 10−3. Formally, let your answer be a, and the jury’s answer be b. Your answer is considered correct if |a−b| max(1,|b|) ≤ 10−3.
standard input
3
0 0 0
3 0 0
0 4 0
4
0 0 0
1 0 0
0 1 0
0 0 1
standard output
2.500000590252103
0.816496631812619
思路:
题意是最小球覆盖,一定要读懂题。
好像是计算几何板子题,不过三个三分也是可以过的,模拟退火玄学算法不清楚。
AC_CODE:
#include <bits/stdc++.h>
#define o2(x) (x)*(x)
using namespace std;
typedef long long LL;
const int MXN = 1e5 + 5;
int n;
int x[MXN], y[MXN], z[MXN];
double len(double X, double Y, double Z, int i) {
return o2(X-x[i])+o2(Y-y[i])+o2(Z-z[i]);
}
double exe3(double X, double Y, double Z) {
double ans = 0;
for(int i = 1; i <= n; ++i) ans = max(ans, len(X,Y,Z,i));
return ans;
}
double exe2(double X, double Y) {
double l = -1e6, r = 1e6, midl, midr, ans;
for(int i = 0; i < 70; ++i) {
midl = (l+r)/2;
midr = (midl+r)/2;
if(exe3(X, Y, midl) <= exe3(X, Y, midr)) {
r = midr, ans = midl;
}else {
l = midl, ans = midr;
}
}
return exe3(X, Y, ans);
}
double exe1(double X) {
double l = -1e6, r = 1e6, midl, midr, ans;
for(int i = 0; i < 70; ++i) {
midl = (l+r)/2;
midr = (midl+r)/2;
if(exe2(X, midl) <= exe2(X, midr)) {
r = midr, ans = midl;
}else {
l = midl, ans = midr;
}
}
return exe2(X, ans);
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%d%d%d", &x[i], &y[i], &z[i]);
double l = -1e6, r = 1e6, midl, midr, ans;
for(int i = 0; i < 70; ++i) {
midl = (l+r)/2;
midr = (midl+r)/2;
if(exe1(midl) <= exe1(midr)) {
r = midr, ans = midl;
}else {
l = midl, ans = midr;
}
}
double tmp = exe1(ans);
printf("%.9f\n", sqrt(tmp));
return 0;
}
最新文章
- 解决:eclipse删除工程会弹出一个对话框提示“[project_name]”contains resources that are not in sync with";[workspace_name...\xx\..xx\..\xx]";
- Markdown工具之---Typora
- webpack的简单使用
- Python 学习---------Day6
- MACOS 答题器,界面跳转
- 【转】MarshalAs属性和使用
- Android 中“TabBar”的背景拉伸问题
- 修改 OWA 修改密码的生效时间
- HDU 2296 Ring (AC自动机+DP)
- Unity3d发布错误:could not allocate memery:system out of memery!
- struts2获取request、session、application
- UDP聊天实现(简单版)
- 谷歌Web中国开发手册:1目的&;amp;夹
- nodejs + nginx + ECS阿里云服务器环境设置
- SmartCoder每日站立会议07
- Web应用程序的敏感信息-隐藏目录和文件
- Android Studio删除依赖
- unity fbx 导出动画
- windows上python的安装
- PHP浮点数的精确计算BCMath