算法难题 - 黑马程序员技术交流社区

问题背景
在平面上有一个长为L，宽为W的长方形，左下角坐标为(0,0)，右上角坐标为(L,W)。给定一些圆，第i个圆的圆心坐标为(xi,yi)，半径为Ri。
你的任务是求最小的正实数k，使得把每个圆的半径变为原来的k倍后（即：第i个圆半径变为kRi，圆心位置不变），长方形将被这些圆完全覆盖。换句话说，长方形内部或边界上的任意点均至少在一个圆的内部或边界上。
输入格式
输入第一行包含三个整数n, L, W（1<=n<=50，1<=L,W<=1000），即圆的个数、长方形的长和宽。
以下n行，每行三个不超过1000的正整数xi, yi和Ri。
输出格式
仅一行，包含一个实数k，保留小数点后三位。
样例输入
1 2 2
1 1 1
样例输出
1.414

package com.itheima.bixiangdong;
public class CircleCover {
/*圆面覆盖问题
问题背景
在平面上有一个长为L，宽为W的长方形，左下角坐标为(0,0)，右上角坐标为(L,W)。给定一些圆，第i个圆的圆心坐标为(xi,yi)，半径为Ri。
你的任务是求最小的正实数k，使得把每个圆的半径变为原来的k倍后（即：第i个圆半径变为kRi，圆心位置不变），长方形将被这些圆完全覆盖。
换句话说，长方形内部或边界上的任意点均至少在一个圆的内部或边界上。
输入格式
输入第一行包含三个整数n, L, W（1<=n<=50，1<=L,W<=1000），即圆的个数、长方形的长和宽。
以下n行，每行三个不超过1000的正整数xi, yi和Ri。
输出格式
仅一行，包含一个实数k，保留小数点后三位。
样例输入
1 2 2
1 1 1
样例输出
1.414*/
public static void main(String[] args) {
/*输入格式我就不写了
* 样例输入
1 2 2
1 1 1
样例输出
1.414*/
System.out.println(getAllMinK(new int[][]{{1,1,1,2,2}}));
/* 样例输入
3 2 2
1 1 1
1 1 2
样例输出
0.707
* */
System.out.println(getAllMinK(new int[][]{{1,1,1,2,2},{1,1,2,2,2}}));
}
public static double getAllMinK(int[][] circle) {
double minK = getMinK(circle[0]);
for(int i=0; i<circle.length; i++) {
double k = getMinK(circle[i]);
if(k<minK)
minK = k;
}
return (int)(minK*1000)/1000.0;
}
/*circle[] x,y,r,l,w*/
public static double getMinK(int... circle) {
double r00 = getC(circle[0]-0 ,circle[1]-0);
double r0w = getC(circle[0]-0 ,circle[1]-circle[4]);
double rl0 = getC(circle[0]-circle[3] ,circle[1]-0);
double rlw = getC(circle[0]-circle[3] ,circle[1]-circle[4]);
/*此最小半径保证此圆完全覆盖长方形*/
double rMax = getMax(r00, r0w, rl0, rlw);
/*此圆最小k*/
return rMax/circle[2];
}
/*勾股定理，你懂的*/
public static double getC(int a, int b) {
return Math.sqrt(a*a+b*b);
}
/*求给定数组的最大元素*/
public static double getMax(double... numble) {
int length = numble.length;
double max = numble[0];
for(int i=1; i<length; i++) {
if(numble[i]>max)
max = numble[i];
}
return max;
}
}

复制代码