圆面覆盖问题

问题背景
在平面上有一个长为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

感觉这个问题还是很有挑战性的，我也不知道能不能做出来，只能说试试吧，喜欢搞算法的都来试试吧，大家看到了就顶一下吧，在有人贴出答案之前，我不想它沉了，如果有人做出来了，我想请求版主给个2分的技术分，毕竟这个题难度不小呢，做出来的请把注释写详细点，便于大家学习，呵呵……睡觉了

顶一下                           

瞧瞧~~~~~~~~~~~~~~~~

啦啦啦，马上升级 金牌黑马~~

顶起                          

这个百度一搜索 一大片 好像百度之星里面什么试题吧  这个我以前看过 没看明白 0 0！！！！

顶一下                     

李志群 发表于 2012-10-4 18:41
这个百度一搜索 一大片 好像百度之星里面什么试题吧  这个我以前看过 没看明白 0 0！！！！ ...

是一道百度之星里面的压轴题呢，40分，等我做出来了再去搜下别人的答案  呵呵

mark下，有点困，明天把后续代码搞定。

代码一枚！！！！问题太多   收回了！！{:soso_e127:}

1. 
   
2. 
   

复制代码

顶一下                        

顶一下，亲们要给力啊

顶                                

1. package com.itheima.bixiangdong;
   
2. 
   
3. public class CircleCover {
   
4. 
   
5.         /*圆面覆盖问题
   
6.         问题背景
   
7.         在平面上有一个长为L，宽为W的长方形，左下角坐标为(0,0)，右上角坐标为(L,W)。给定一些圆，第i个圆的圆心坐标为(xi,yi)，半径为Ri。
   
8.         你的任务是求最小的正实数k，使得把每个圆的半径变为原来的k倍后（即：第i个圆半径变为kRi，圆心位置不变），长方形将被这些圆完全覆盖。
   
9.         换句话说，长方形内部或边界上的任意点均至少在一个圆的内部或边界上。
   
10.         输入格式
    
11.         输入第一行包含三个整数n, L, W（1<=n<=50，1<=L,W<=1000），即圆的个数、长方形的长和宽。
    
12.         以下n行，每行三个不超过1000的正整数xi, yi和Ri。
    
13.         输出格式
    
14.         仅一行，包含一个实数k，保留小数点后三位。
    
15.         样例输入
    
16.         1 2 2
    
17.         1 1 1
    
18.         样例输出
    
19.         1.414*/
    
20.        
    
21.         public static void main(String[] args) {
    
22.                
    
23.                 /*输入格式我就不写了
    
24.                  * 样例输入
    
25.                         1 2 2
    
26.                         1 1 1
    
27.                         样例输出
    
28.                         1.414*/
    
29.                 System.out.println(getAllMinK(new int[][]{{1,1,1,2,2}}));
    
30.                
    
31.                 /* 样例输入
    
32.                         3 2 2
    
33.                         1 1 1
    
34.                         1 1 2
    
35.                         样例输出
    
36.                         0.707
    
37.                  * */
    
38.                 System.out.println(getAllMinK(new int[][]{{1,1,1,2,2},{1,1,2,2,2}}));
    
39.         }
    
40.        
    
41.         public static double getAllMinK(int[][] circle) {
    
42.                 double minK = getMinK(circle[0]);
    
43.                  
    
44.                 for(int i=0; i<circle.length; i++) {
    
45.                         double k = getMinK(circle[i]);
    
46.                         if(k<minK)
    
47.                                 minK = k;
    
48.                 }
    
49.                 return (int)(minK*1000)/1000.0;
    
50.         }
    
51.        
    
52.         /*circle[] x,y,r,l,w*/
    
53.         public static double getMinK(int... circle) {
    
54.                 double r00 = getC(circle[0]-0                        ,circle[1]-0);
    
55.                 double r0w = getC(circle[0]-0                        ,circle[1]-circle[4]);
    
56.                 double rl0 = getC(circle[0]-circle[3]        ,circle[1]-0);
    
57.                 double rlw = getC(circle[0]-circle[3]        ,circle[1]-circle[4]);
    
58.                
    
59.                 /*此最小半径保证此圆完全覆盖长方形*/
    
60.                 double rMax = getMax(r00, r0w, rl0, rlw);
    
61.                
    
62.                 /*此圆最小k*/
    
63.                 return rMax/circle[2];
    
64.         }
    
65.        
    
66.         /*勾股定理，你懂的*/
    
67.         public static double getC(int a, int b) {
    
68.                 return Math.sqrt(a*a+b*b);
    
69.         }
    
70.        
    
71.         /*求给定数组的最大元素*/
    
72.         public static double getMax(double... numble) {
    
73.                 int length = numble.length;
    
74.                 double max = numble[0];
    
75.                 for(int i=1; i<length; i++) {
    
76.                         if(numble[i]>max)
    
77.                                 max = numble[i];
    
78.                 }
    
79.                 return max;
    
80.         }
    
81. }

复制代码

下午发的代码中，这个函数有问题，修改如下：

1. public static double getAllMinK(int[][] circle) {
   
2.                 double minK = getMinK(circle[0]);
   
3.                  
   
4.                 for(int i=0; i<circle.length; i++) {
   
5.                         double k = getMinK(circle[i]);
   
6.                         if(k<minK)
   
7.                                 minK = k;
   
8.                 }
   
9.                 return (int)(minK*1000)/1000.0;
   
10.         }

复制代码

寇龙飞 发表于 2012-10-9 00:04
我来了，求测试数据。

你只做了一个圆的情况啊，这个就很简单了，关键是题目中说的可以有多个圆呢，如果我给你3个圆，你把这3个圆的圆心到这个矩形的4个顶点的距离求出来再从中取个最大的值来做为最小半径，那这样就错了

柏占肖 发表于 2012-10-10 17:57
你只做了一个圆的情况啊，这个就很简单了，关键是题目中说的可以有多个圆呢，如果我给你3个圆，你把这3个 ...

1. for(int i=0; i<circle.length; i++) {
   
2.                         double k = getMinK(circle[i]);
   
3.                         if(k>minK)
   
4.                                 minK = k;
   
5.                 }

复制代码

我知道你题目的要求，这里写了for循环的亲。
所以，我发代码时也说了，要测试数据啊，你给三个圆的数据就是了。

寇龙飞 发表于 2012-10-10 18:22
我知道你题目的要求，这里写了for循环的亲。
所以，我发代码时也说了，要测试数据啊，你给三个圆的数据就 ...

再给简单点，两个圆，一个大圆，它已经把这个矩形覆盖了，再给个小圆，它没有把矩形覆盖，按你的这个算法算出来就是它们的半径还需要放大，这很明显就错了

柏占肖 发表于 2012-10-10 18:30
再给简单点，两个圆，一个大圆，它已经把这个矩形覆盖了，再给个小圆，它没有把矩形覆盖，按你的这个算法 ...

嗯。了解。是我那个getAllMinK函数中变量minK初始化错误，导致if(k与minK)的判断逻辑错误。

现在偶了。。。14楼代码

寇龙飞 发表于 2012-10-10 20:42
嗯。了解。是我那个getAllMinK函数中变量minK初始化错误，导致if(k与minK)的判断逻辑错误。

现在偶了。 ...

不行啊，你的这个思想不对，以你的算法算出和结果就是我给你N个圆，半径改变后，至少有一个圆是把整个矩形都覆盖了的，但是题目并不是这个意思，打个比方，就好比树下的阴影，那么大一块阴影并不是因为哪一片叶子挡住了阳光而形成的，而是因为很多叶子拼凑在一起而形成的，在这里，圆就好比叶子，矩形就好比树下的阴影。
这个题还是有一些难度的，等我把视频面试过了就来整它了，个人觉得这个要先把倍数的取值范围求出来，然后再用折半法来找出最小且满足题目要求的倍数

柏占肖 发表于 2012-10-10 21:41
不行啊，你的这个思想不对，以你的算法算出和结果就是我给你N个圆，半径改变后，至少有一个圆是把整个矩 ...

“换句话说，长方形内部或边界上的任意点均至少在一个圆的内部或边界上。”


怎么说