| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3674 人关注过本帖
标题:求圆包含点集的元素的最大个数~
只看楼主 加入收藏
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 10楼 九转星河
顺便更新一下四楼的思路~

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

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

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-04-22 05:23
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
知道方法了折腾了半天竟然得出了如此简单有力的思维方法~~~~~~~~

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

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


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-04-22 05:57
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
收藏
得分:100 
回复 12楼 九转星河
程序代码:
#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;        ///< 斜率存在否 0不存在  1存在
    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;                    ///< 斜率存在否 0不存在  1存在
                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;
}
2017-04-23 23:21
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
收藏
得分:0 
回复 12楼 九转星河
改动了下计算是否在圆内关系判断

没有细测

大概方法是
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-04-23 23:34
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 14楼 寒风中的细雨
对哦~有道理~想到了~一个点表示一个圆~两个点表示两个圆~两个圆的交集区域就是表示能包含两个点的区域~其实就是求重合区域的最大重合次数~两个圆的的弦必然在这个交集里面~新增一个(点)圆~就会有三条公共弦~就是求这些公共弦的交点有包含了多少个点~这个逻辑上是行得通的~

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


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


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-04-24 02:43
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 13楼 寒风中的细雨
100分全送你了~~~~~~~现在还有别的任务----无论是编程任务还是学习任务~~~代码找到时间再慢慢细测~~~~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-04-24 02:46
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 14楼 寒风中的细雨
感觉原理上没有错~不过我看了13楼的代码还是有一个疑问~公共弦应该是一条线段而不是一条直线~所以13楼代码说是求两条直线的交点到到两个端点的任意一个距离是否大于该线段长度这个条件判断?~我没有细看代码~如果代码有考虑此情况就原谅我多问了~~


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

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


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-04-24 06:02
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
收藏
得分:0 
回复 17楼 九转星河
线段  所在的直线

如果圆之间有公共区域, 两线段 的交点  会在 公共区域的(即 线段上)

2017-04-24 23:59
快速回复:求圆包含点集的元素的最大个数~
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.068578 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved