顺便更新一下四楼的思路~

就是选一个定点，求该定点能被圆包含的点集的最大子集。该点在动圆上的圆心轨迹为半径r的圆i。以这个点作一个半径为2r的圆j，遍历该范围包含的点作一个圆k，k和i的轨迹有一个或者两个交点。选其cos值与垂直方向夹角小的画一个圆l，然后再遍历该圆l里面的点集。

就是求所有圆l里面点集的最大值。~这算法复杂度应该介于0(n^2/2)到0(n^3/2)之间(按逐个逐个点插入优化效率可以提高到原来的两倍)~圆越大算法复杂度越高~~

知道方法了折腾了半天竟然得出了如此简单有力的思维方法~~~~~~~~

已知圆的半径和两个定点能确定一个或者两个定圆，这个圆也有可能不存在的~~然后找到该圆心遍历点集是否在圆内~就是进行边界检测~
经过优化选方程的两个解其中之一算法复杂度也是在0(n^2/2)到0(n^3/2)之间~其实实质就是11楼的另一种说法~~

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

#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 line_st{
    
    unsigned int     is_ek;        ///<　斜率存在否　０不存在　　１存在
    double k;    ///< 斜率 y = kx + b
    double b;    ///< 如果斜率不存在 表示 x的坐标
}line_st;
/**

 *\brief 集合

 */
typedef struct set_st{
    
    unsigned int    idx_list[MAX_POINTS];    ///< 点的下标值
    unsigned int    count;                    ///< 集合的规模
    line_st            line;                    ///< 第一、二圆的公共弦 所在的直线
}set_st;

static unsigned int s_points_num;    ///< 输入的点数量
static double     s_r;        ///< 半径长度
static point_st s_points[MAX_POINTS];    ///< 点列表
static unsigned int s_sets_num;
static set_st    s_sets[MAX_POINTS*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_collision_point(line_st *l_1, line_st *l_2, point_st *point)
{
    if (l_1->is_ek == 0 && l_2->is_ek == 1){
        
        point->x = l_1->b;
        point->y = l_2->k * point->x + l_2->b;
        return 1;
    }else if (l_1->is_ek == 1 && l_2->is_ek == 0){
        
        point->x = l_2->b;
        point->y = l_1->k * point->x + l_1->b;        
        return 1;
    }else if (l_1->is_ek == 1 && l_2->is_ek == 1){
        
        point->x = (l_1->b - l_2->b)/(l_2->k - l_1->k);
        point->y = l_1->k * point->x + l_1->b;
        
        return 1;
    }
    
    return 0;
}

/**

 *\brief 求最大覆盖

 */
static int get_max_cover(void)
{
    unsigned int i = 0, j = 0, k = 0, max = 0;
    
    s_sets_num = 0;
    for (i = 0; i < s_points_num; ++i){
        
        for (j = i + 1; j < s_points_num; ++j){
            
            if (2 * s_r < get_dis(i, j)){
                
                continue;
            }
            
            s_sets[s_sets_num].idx_list[0] = i;
            s_sets[s_sets_num].idx_list[1] = j;
            s_sets[s_sets_num].count = 2;
            if (s_points[i].y == s_points[j].y){// 斜率不存在
                
                s_sets[s_sets_num].line.is_ek = 0;    // x = (pi.x + pi.x)/2
                s_sets[s_sets_num].line.b = (s_points[j].x + s_points[i].x)/2.0;
            }else{
                
                s_sets[s_sets_num].line.is_ek = 1;
                s_sets[s_sets_num].line.k = (s_points[j].x - s_points[i].x)/(s_points[i].y - s_points[j].y);
                s_sets[s_sets_num].line.b = (pow(s_points[i].x,2.0) + pow(s_points[i].y,2.0) - pow(s_points[j].x, 2.0) - pow(s_points[j].y, 2.0))/(2*(s_points[i].y - s_points[j].y));
            }
            ++s_sets_num;
        }
    }
        
    for (i = 0; i < s_points_num; ++i){// 遍历所有的点
        
        for (j = 0; j < s_sets_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){
                
                // 取集合中第一个点与该点相交 会获得一个直线
                unsigned int    idx;                    ///<　斜率存在否　０不存在　　１存在
                line_st    line;
                point_st point;
                
                idx = s_sets[j].idx_list[0];
                if (s_points[idx].y == s_points[i].y){// 斜率不存在
                
                    line.is_ek = 0;    // x = (pi.x + pi.x)/2
                    line.b = (s_points[idx].x + s_points[i].x)/2.0;
                }else{
                
                    line.is_ek = 1;
                    line.k = (s_points[idx].x - s_points[i].x)/(s_points[i].y - s_points[idx].y);
                    line.b = (pow(s_points[i].x,2.0) + pow(s_points[i].y,2.0) - pow(s_points[idx].x, 2.0) - pow(s_points[idx].y, 2.0))/(2*(s_points[i].y - s_points[idx].y));
                }
                
                // 求2直线的交点 
                get_collision_point(&s_sets[j].line, &line, &point);
                
                for (k = 0; k < s_sets[j].count; ++k){// 遍历集合中的点
                                
                    idx = s_sets[j].idx_list[k];
                    if (pow(point.x - s_points[idx].x,2.0) + pow(point.y - s_points[idx].y,2.0) > 1){
                        
                        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_sets_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;
}

改动了下计算是否在圆内关系判断

没有细测

大概方法是
1、在 平面上 选择符合条件的点对， 即2个圆，构成点集P， 同时记录下这两圆的公共弦（y = k1x + b1）
2、在新的点（圆）加入的时候 从集合P中任找一个点（圆） 进行相交， 也获得一个公共弦(y = k2x + b2)
    求2个 公共弦的交点 J(x,y)
3、如果 交点J 满足 在集合P中的所有点(圆） 都存在有(Px - Jx)^2 + (Py - Jy)^2 <= 1， 则将新的点加入到集合P中，
   否则不满足。

对哦~有道理~想到了~一个点表示一个圆~两个点表示两个圆~两个圆的交集区域就是表示能包含两个点的区域~其实就是求重合区域的最大重合次数~两个圆的的弦必然在这个交集里面~新增一个(点)圆~就会有三条公共弦~就是求这些公共弦的交点有包含了多少个点~这个逻辑上是行得通的~

说个题外话~神奇的是三条公共弦实际如果有交点实际上只有一个交点~这个交点似乎是三个圆的六个交点外三个交点组成的和里面三个组成的三角形的什么心~~以前想利用平面几何证明~无奈变量太多做不了(后来看到网上有高手能用简洁的数学语言证明出来就笑哭了)~~

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

100分全送你了~~~~~~~现在还有别的任务----无论是编程任务还是学习任务~~~代码找到时间再慢慢细测~~~~

感觉原理上没有错~不过我看了13楼的代码还是有一个疑问~公共弦应该是一条线段而不是一条直线~所以13楼代码说是求两条直线的交点到到两个端点的任意一个距离是否大于该线段长度这个条件判断？~我没有细看代码~如果代码有考虑此情况就原谅我多问了~~


PS:这条题方法还可以再改进一下~可以不用求直线表达式~就是求两个圆的交点能被多少个圆包含~这样理解就变得非常简单了~~~~~~~~~

[此贴子已经被作者于2017-4-24 06:45编辑过]

线段  所在的直线

如果圆之间有公共区域， 两线段 的交点  会在 公共区域的（即 线段上）