点击打开链接 (这个链接到BNUOJ上面是一样的)
题目意思: 给定m个圆的半径,现在要求找到一个矩形使得每一个球都以地面相切,要求输出最小的矩阵的长度
解题思路: 最小的圆排列问题,对于这样的一个图形我么是转化为坐标来计算,那么我们需要做的三个步骤就是 1 递归去放入每一个圆 2 求出每一个圆的圆心的横坐标 3计算最小的长度 。 具体过程见代码分析:
代码:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
int n , m;
double r[10];//用来存储每一个圆的半径
double p[10];//存储圆的横坐标
double ans;
//求解第k个圆的横坐标函数(也就是说,第k个圆很可能跟前面任何一个圆相切。这时,只要把各种情况得到取值全部算出,并把最大值 记录下来)
//我们知道对于从左往右的所有的圆来说,圆心的横坐标都是增大,不用考虑圆的大小,那么对于k这个圆,它是最右边的那么我们找到最大的横坐标才是它的横坐标值
double Point(int k){
double R = 0;
for(int j = 1 ; j < k ; j++){
double tempr = p[j] + 2.0*sqrt(r[k]*r[j]);//两个圆的距离 d = sqrt((r1+r2)^2 - (r1-r2)^2) 那么有 d = 2.0*sqrt(r[k]*r[j]);
if(R < tempr)//更新为最大
R = tempr;
}
return R;
}
//计算当前的圆排列的长度
//p[i]-r[i],就是该圆最左边的切线的横坐标 p[i]+r[i]就是该圆最右边的切线的横坐标,那么对于这个圆排列的长度就是最右边的横坐标减去最左边的横坐标
void Distance(){
double high , low;
high = 0 ; low = 0;
for(int i = 1 ; i <= m ; i++){
if(p[i]-r[i] < low) low = p[i] - r[i]; //更新最左边的位置
if(p[i]+r[i] > high) high = p[i] + r[i]; //更新最右边的位置
}
if(high - low < ans)
ans = high - low;//更新最小距离
}
//回溯搜索函数
void dfs(int k){
if(k > m)//圆放完后就是计算这个排列的长度
Distance();
else{
for(int j = k ; j <= m ; j++){
swap(r[k] , r[j]);//考虑放入k后,序列长度; 还要考虑继第k个球之后,余下的m-k个球放入后,对整个序列的长度的影响.
double R = Point(k);
if(R+r[k]+r[1] < ans){//满足条件继续递归
p[k] = R;
dfs(k+1);
}
swap(r[k] , r[j]);//现场的恢复
}
}
}
//主函数
int main(){
scanf("%d" , &n);
while(n--){
scanf("%d" , &m);
memset(r , 0.0 , sizeof(r));
memset(p , 0.0 , sizeof(p));
for(int i = 1 ; i <= m ; i++)
scanf("%lf" , &r[i]);
p[1] = 0.0;//规定第一个点的横坐标为0
ans = 999999999;
dfs(1);
printf("%.3lf\n" , ans);//输出的格式
}
return 0;
}
分享到:
相关推荐
UVA 10474
UVA109的题解,经测试完全正确,还附有题解。
uva272
包含UVA在线OJ系统的绝大部分的示例代码,并都已AC,可在刷题时参考
有uva刘汝佳文件夹的50道题解,从数据结构开始,以后慢慢上传
UVa在我看来是比较全的一个题解,希望能帮助大家。欢迎下载。
uva最全ac代码
uva531最长公共子序列问题水题,应用简单的dp即可ac有更快速的方法欢迎讨论
uva10755 ac 代码,可以随意更改下载
uva357的栈实现版本
UVA 题目,不是很难,试试吧
《算法竞赛入门经典》UVa配套题目pdf版完整
世界著名大学UVA OJ平台上的题目部分分类,分的不好请原谅。
1.Uva_base的编译 在编译球队时,则需要在当前球队文件夹下打开终端输入执行以下命令(以下命令都是在root下执行的): ./configure make clean make 如果运行Uva_base后,出现球员越界或掉线的情况,就重新...
uva_trilearn2002 源代码
这是一支完整的uva球队,包含所有基本模块,初者可在上修改得到自己的球队
PDF试题
主要是uvaoj习题相关题目 练习题目
这里面全部为在Uva Online Judge上面的部分题目的解答,里面提供了解答使用的源代码。
开源项目-codingsince1985-UVa.zip,Been solving UVa Online Judge Problems in Golang for one year (and counting)