现在二维坐标系里面有n个点,第i个点的坐标为(xi,yi)。
求在二维坐标系里面选择一个恰当的坐标作一个半径为r的圆，包含的点集的元素个数最多。

输入:
第一行输入两个数，第一个数是点个数n，第二个数是圆的半径r，两个输入之间用空格隔开。
然后接下来n行每行输入两个数，第一个数是第i个点的横坐标，第二个数是第i个点的纵坐标，两个输入之间用空格隔开。
输出:一行，该圆能够包含的点集的元素最大个数。

例子:
输入:
9 1
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
输出:
5

感觉这题思路应该是进行边界检测~想到思路的是求对每个点用动圆来边界检测其圆内包含点的个数。
但感觉把面量化成点来检验很有难度~现在我往如何才能把面量化为点来检验这个方面去想。
~感觉这题和平面几何有关系啊~不过还是对具体解法不清楚~具体怎么实现就说不出来了~这题感觉难度很大~现在我对解出这题的期望也不太高~不过还是可以尽量尝试一下吧~~~

循环求两点间的距离  距离小于 2r 的归类到一个点集

后续新的点就和集合中所有的点 进行距离计算   符合距离都小于  2r的就加入到集合中


遍历完所有的点后，  找出集合中点最多的就是解

这个应该是 中心选址 问题

如果选址在点上当然简单~但问题是选址不一定在题目给出的某个点上~圆心可以是二维空间的任意位置~这个才是棘手的地方。

想了很久想到了一种数学解法，对每个点进行分析，在选取点i上画一个半径为2r的圆，然后搜索其在2r里面的点。找到该点j再画一个半径为r的圆~这个圆会与以点i为圆心r为半径的圆有一个或者两个交点。按顺时针记录其中一个交点为记作+，另一个交点为-，遇到+就把max+1，遇到-就把max-1。然后统计该圆里面的max的最大值。

对所有点逐一比对~求这个max的最大值。

时间复杂度和点的稠密与否直接相关。

感觉为0(K*n^2)~~K为每个圆最多平均包含的点数~

[此贴子已经被作者于2017-4-22 04:51编辑过]

最坏的情况 是  O(n^2)

在不在给出的点上  算法都差不多

和二楼一并回复~这样大概看看不出什么问题~这个方法可以考虑验证一下~如果该方法成立则代码比我想到的那个更优更简了~~~~~

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>

#define MAX_POINTS    (100)    ///<

/**

 *\brief 点

 */
typedef struct point_st{

    double    x;
    double    y;
}point_st;

/**

 *\brief 集合

 */
typedef struct set_st{
    
    unsigned int    idx_list[MAX_POINTS];    ///< 点的下标值
    unsigned int    count;                    ///< 集合的规模
}set_st;

static unsigned int s_points_num;    ///< 输入的点数量
static double     s_r;        ///< 半径长度
static point_st s_points[MAX_POINTS];    ///< 点列表
static set_st    s_sets[MAX_POINTS];        ///< 点集

/**

 *\brief 捕获终端输入

 */
static int get_input(void)
{
    unsigned int i = 0;
    
    scanf("%u %lf", &s_points_num, &s_r);
    
    assert(MAX_POINTS >= s_points_num);
    
    for (i = 0; i < s_points_num; ++i){
        
        scanf("%lf %lf", &s_points[i].x, &s_points[i].y);
    }
    
    return 0;
}

/**

 *\brief 求两点间的距离

 */
static inline double get_dis(unsigned int i, unsigned int j)
{
    double x, y;
    
    x = pow(s_points[i].x - s_points[j].x, 2.0);
    y = pow(s_points[i].y - s_points[j].y, 2.0);
    
    return sqrt(x + y);
}

/**

 *\brief 求最大覆盖

 */
static int get_max_cover(void)
{
    unsigned int i = 0, j = 0, k = 0, max = 0;
    
    for (i = 0; i < s_points_num; ++i){
                    
        s_sets[i].idx_list[0] = i;
        s_sets[i].count = 1;
    }
        
    for (i = 0; i < s_points_num; ++i){// 遍历所有的点
        
        for (j = 0; j < s_points_num; ++j){// 遍历所有的集合
            
            for (k = 0; k < s_sets[j].count; ++k){// 遍历集合中的点
                
                if (s_sets[j].idx_list[k] == i){
                    
                    break; // 同一个点
                }
                
                if (2 * s_r < get_dis(i, s_sets[j].idx_list[k])){
                    
                    break;
                }
            }
            
            if (k >= s_sets[j].count){
                
                s_sets[j].idx_list[s_sets[j].count] = i;
                ++s_sets[j].count;                
            }
        }
    }
    
    for (i = 0; i < s_points_num; ++i){
        
        if (max < s_sets[i].count){
            
            max = s_sets[i].count;
        }
    }
    
    printf("\tres[%u]\n", max);
    
    return 0;
}

int main(void)
{
    get_input();
    
    get_max_cover();
    
    return 0;
}

~/test # ./tests
9 1
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
    res[5]

最好的是 O(n^2)
最坏的是 0(n^3)  所有的点都落在圆内

是的~算法复杂度和我想到的一样~感觉解法比我想到的要简单一些~这个代码虽然还没细测~但应该可以~

这是一个等边三角形~
难怪看了代码看了很久还是理解不了……感觉是方法问题~这题感觉没那么简单~~~~