首页 / 算法 / 【算法学习笔记】32.计算几何 求含最多给定点的直线 SJTU OJ 1350 穿越沙漠

【算法学习笔记】32.计算几何 求含最多给定点的直线 SJTU OJ 1350 穿越沙漠

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法学习笔记】32.计算几何 求含最多给定点的直线 SJTU OJ 1350 穿越沙漠，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4245字，纯文字阅读大概需要7分钟。

内容图文

1350. 穿越沙漠

Description

塞尔达公主又又又又被抓走了。林克为了找到她需要穿过拉纳鲁沙漠，坏消息是林克可能没有足够的体力穿越沙漠，好消息是沙漠中分布着N个力之果实，坏消息是我们的林克只能走直线。为了穿越沙漠，林克希望能够吃到尽可能多的力之果实。现在请你帮他规划一条直线，使他能够获得尽可能多的力之果实。

Input Format

输入第一行有一个数N，表示沙漠中果实的数量。

接下来的N行每行两个正整数x,y，表示每个力之果实的坐标。

Output Format

输出一个数，表示林克最多能够获得的力之果实的数量。

Sample Input

            5
4 4
2 2
9 9
9 11
17 8

Sample Output

            3

说明

对于70%的数据，N<=300

对于100%的数据，N<=700

 

第一种方法: O(n^3)

任取两个点,i j 作为一条直线, 对剩下的所有点中遍历是否在这条直线上. 维护最大值即可,

几点注意的地方:

1.三重循环的起始和结束: 因为i j 和 j i 组成的是同一条直线 所以可以避免重复 . 而k也同样  如果在前面出现过 那么一点计算过 所以不用考虑

或者换一种思路 认为 i是要进行判断的点, j 和 k组成的是直线,所以由刚才的思路 也可以减少循环量.

或者再换一种思路, 认为每个在同一条直线上的所有点组成了给定点集的一个子集, 这个子集至少有两个不重复点, 剩下每次加入一给点都可以认为它是第三个点,所以也要不重复,并且关于三点共线的公式可以直接套用外积公式. 

2.能用乘法不要用除法. 这个算是常识吧..好好的整数运算就可以解决的问题搞一个浮点数出来多傻呀..不仅慢 还 占空间.

代码如下:

技术分享 技术分享 
                    /*
                    
Judging... PROB=1350 LANG=C++

Accepted (Time: 6ms, Memory: 4968kb)
Accepted (Time: 6ms, Memory: 4964kb)
Accepted (Time: 5ms, Memory: 4956kb)
Accepted (Time: 6ms, Memory: 4952kb)
Accepted (Time: 8ms, Memory: 4968kb)
Accepted (Time: 11ms, Memory: 4956kb)
Accepted (Time: 17ms, Memory: 4964kb)
Accepted (Time: 140ms, Memory: 4960kb)
Accepted (Time: 262ms, Memory: 4968kb)
Accepted (Time: 187ms, Memory: 4952kb)

                    */
                    
#include <iostream>
usingnamespace std;
 
int x[701]={0},y[701]={0};//700个点int main(int argc, charconst *argv[])
{
    int n; cin>>n;
    for (int i = 0; i < n; ++i)
    {
        cin>>x[i]>>y[i];
    }
    //Cn2 枚举两个点 确定一条直线
    //然后 枚举每个点 判断三点是否共线int max  = 2;
    for (int i = 0; i < n-2; ++i)
    {
        for (int j = i+1; j < n-1; ++j)
        {
            int count = 2;
            //i 和 j 组成了一条直线if(x[i]==x[j] and y[i]==y[j])
                continue;
            for (int k = j+1; k < n; ++k)
            {
                //研究k点是否在 i j 直线上bool isOn = ( (y[j]-y[i])*(x[k]-x[i]) == (x[j]-x[i]) *(y[k]-y[i]) );
                if(isOn)
                    count++;
            }
            if(count > max)
                max = count;
        }
    }
    cout<<max<<endl;
    return0;
}
O(n^3)

 

第二种方法稍微优化了一点.其实也就是O(n^2lgn)和O(n^3)的区别, 但是效果也是很显著的.(可以对比一下耗时)

思想就是,先找到一个点i,算出其他点和这个点的斜率,然后从这个斜率集合中找到重复出现次数最多的次数,这个次数表名了有多少个点在i的同一延伸方向上,在加上i本身,那么就能得到"在某一条含有i的直线与给定点集的交集的大小". 再从这些值中找到最大的 那就是答案.

这个的优化本质是: 在第一种方法里,每次取三个点进行判断时,其实重复计算了某些斜率 比如当 i j k 和 i k n 活着j k m 时  i k 和 j k的斜率都是重复计算的,

而我们只要根据i,j 给定的i 任意的j 算出斜率 取出频率最高的那个斜率 就找到了一条待定直线.

具体代码如下:

技术分享 技术分享 
                /*
                
Judging... PROB=1350 LANG=C++

Accepted (Time: 7ms, Memory: 4968kb)
Accepted (Time: 8ms, Memory: 4956kb)
Accepted (Time: 5ms, Memory: 4948kb)
Accepted (Time: 6ms, Memory: 4960kb)
Accepted (Time: 7ms, Memory: 4988kb)
Accepted (Time: 9ms, Memory: 4976kb)
Accepted (Time: 12ms, Memory: 4980kb)
Accepted (Time: 40ms, Memory: 4984kb)
Accepted (Time: 50ms, Memory: 4996kb)
Accepted (Time: 44ms, Memory: 4988kb)

                */
                

#include <iostream>
#include <algorithm>
#include <cmath>
usingnamespace std;
 
int x[701]={0},y[701]={0};//700个点struct fraction
{
    int son;
    int mom;
    booloperator == (const fraction& b)const
    {
        return (son*b.mom == b.son*mom);
    }
    booloperator != (const fraction &b)const
    {
        return1-(*this==b);
    }
};
fraction scopes[700];
int freqs[700]={0};
 
int cmp_fraction(constvoid* _a, constvoid* _b){
    fraction* a = (fraction*) _a;
    fraction* b = (fraction*) _b;
    return (*a).son * (*b).mom - (*b).son * (*a).mom;
}
 
 
int main(int argc, charconst *argv[])
{
    int n; cin>>n;
    for (int i = 0; i < n; ++i)
    {
        cin>>x[i]>>y[i];
    }
    //针对每个固定点 枚举后继点 确定斜率
    int max  = 2;
    int freqs_len = 0;
    for (int i = 0; i < n-1; ++i)
    {
        //确定经过i点的所有直线的斜率集合 根据这个集合里重复数的个数的最多 即是 含有i点的子集中最多的数量
        //每次的scopes 集合都要更新 只需记录长度即可int len = 0;
        int same = 0;
        for (int j = i+1; j < n; ++j)
        {
            if(x[i]==x[j] and y[i]==y[j]){
                same++;
                continue;
            }
            fraction k;
            k.son = abs(y[j]-y[i]);//不加不行 - -
            k.mom = abs(x[j]-x[i]);
            scopes[len++] = k;
        }
        //排序 O(nlgn)
        qsort(scopes,len,sizeof(fraction),cmp_fraction);
        //计算频率最多 O(n)int maxFreq = 1;
        int freq = 1;
        for (int j = 1; j < len; ++j)
        {
            if(scopes[j]==scopes[j-1])
                freq++;
            else{//断了if(freq>maxFreq)
                    maxFreq = freq;
                freq = 1;
            }
        }
        if(freq>maxFreq)
            maxFreq = freq;
        freqs[freqs_len++] = maxFreq + 1 + same;//加上i自己    }
    for (int i = 0; i < freqs_len; ++i)
    {
        if(max < freqs[i])
            max = freqs[i];
    }
    cout<<max<<endl;
    return0;
}
O(n^2lgn)

 

此处用到了结构体来表示分数,而不用浮点数,是因为浮点数计算和判断浮点数相等的过程比较麻烦(虽然代码没这个麻烦,但是计算机计算的时候应该会比这个麻烦)注意qsort函数的使用,

另外有几个细节是

1.存储时一定要统一用abs来存储,否则进行排序时会有问题,

2.用same变量来保存相同的点 这个在第一种方法里也要考虑到

 

原文：http://www.cnblogs.com/yuchenlin/p/4449123.html

内容总结

以上是互联网集市为您收集整理的【算法学习笔记】32.计算几何 求含最多给定点的直线 SJTU OJ 1350 穿越沙漠全部内容，希望文章能够帮你解决【算法学习笔记】32.计算几何 求含最多给定点的直线 SJTU OJ 1350 穿越沙漠所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1156241.html

来源：【匿名】