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

浏览数：108 / 时间：2015年06月08日

Description

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

Input Format

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

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

Output Format

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

Sample Input

Sample Output

说明

对于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>
using namespace std;
 
int x[701]={0},y[701]={0};//700个点
 
int main(int argc, char const *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;
    return 0;
}

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>
using namespace std;
 
int x[701]={0},y[701]={0};//700个点
 
 
struct fraction
{
    int son;
    int mom;
    bool operator == (const fraction& b)const
    {
        return (son*b.mom == b.son*mom);
    }
    bool operator != (const fraction &b)const
    {
        return 1-(*this==b);
    }
};
fraction scopes[700];
int freqs[700]={0};
 
int cmp_fraction(const void* _a, const void* _b){
    fraction* a = (fraction*) _a;
    fraction* b = (fraction*) _b;
    return (*a).son * (*b).mom - (*b).son * (*a).mom;
}
 
 
int main(int argc, char const *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;
    return 0;
}