圆面覆盖问题

问题背景
在平面上有一个长为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分的技术分，毕竟这个题难度不小呢，做出来的请把注释写详细点，便于大家学习，呵呵……睡觉了

寇龙飞 发表于 2012-10-11 23:35
嗯。我还是没学好知识，理解力不够。悔不当初，只能现在努力勒。

嗯   加油               

寇龙飞 发表于 2012-10-11 23:35
嗯。我还是没学好知识，理解力不够。悔不当初，只能现在努力勒。

嗯   加油

柏占肖 发表于 2012-10-11 22:49
呵呵……有些大赛的题就是不好读，ACM的更是  像文言文一样

嗯。我还是没学好知识，理解力不够。悔不当初，只能现在努力勒。

寇龙飞 发表于 2012-10-11 22:46
嗯。终于想通了，你说的是对的。群圆覆盖长方形。

呵呵……有些大赛的题就是不好读，ACM的更是  像文言文一样

柏占肖 发表于 2012-10-11 22:30
我上面贴了两张图的  你好好看看吧   我以为是百度之星的题呢  结果我一个耍得好的说是ITAT的最后一道题  ...

嗯。终于想通了，你说的是对的。群圆覆盖长方形。

寇龙飞 发表于 2012-10-11 22:12
不管题目难易，咱主要是看满足题目覆盖的条件是什么。

我上面贴了两张图的  你好好看看吧   我以为是百度之星的题呢  结果我一个耍得好的说是ITAT的最后一道题   这题真的不是你理解的那样啊

柏占肖 发表于 2012-10-11 21:37
你理解错了   照你那样理解的话这题也太简单了

不管题目难易，咱主要是看满足题目覆盖的条件是什么。

寇龙飞 发表于 2012-10-11 20:44
no

不是多个圆最小的共同努力下覆盖长方形，而是最小努力下某一个最合适的圆覆盖长方形 ...

你理解错了   照你那样理解的话这题也太简单了

柏占肖 发表于 2012-10-11 13:09
如果用多个圆来覆盖，在矩形内部可能就有圆与圆的重合，那么这时矩形内部的的有些点可能就同时在多个圆的 ...

no

不是多个圆最小的共同努力下覆盖长方形，而是最小努力下某一个最合适的圆覆盖长方形

说实话看懂这个题目还要花点时间呢

我看看。。

寇龙飞 发表于 2012-10-11 11:56
“换句话说，长方形内部或边界上的任意点均至少在一个圆的内部或边界上。”

如果用多个圆来覆盖，在矩形内部可能就有圆与圆的重合，那么这时矩形内部的的有些点可能就同时在多个圆的内部或边界上了，题目中说至少，也就是说矩形中的每一点都要被覆盖

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

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


怎么说

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

现在偶了。 ...

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

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

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

现在偶了。。。14楼代码

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

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

柏占肖 发表于 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-9 00:04
我来了，求测试数据。

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

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.         }

复制代码