POJ 1118 Lining Up(点与直线)

POJ 1118 Lining Up(点与直线)

http://poj.org/problem?id=1118

题意: 同POJ2780 POJ2606

给你n个二维平面点的坐标,问你最多有多少个点共线?

分析:

首先我们直观的方法是找出所给点集的所有可能的直线,然后对于每条直线,看看有多少个其他的点在该直线上. 最后更新最大值即可.

程序1实现找用到了定序的技巧,保证不会丢失最优解. 比如某条直线上有5个点且是最多的.这5个点分别编号为1,4,5,7,8.那么我们用下面第2种方式来实现代码:

可以看到1肯定是i, 4肯定是j, 然后k分别遍历到了5,7,8.

暴力枚举见代码1.

下面是通过排序来降低一点复杂度的方法二.

我们枚举每一个点,把该点作为固定点,然后我们计算剩下的所有点与该点构成直线的斜率(注意处理斜率不存在的情况),把这些斜率保存在数组S中,然后对S数组排序,那么斜率相同的值就会变成连续存放.那些斜率相同的值就代表的共线的点,这样就可算出最多有多少点共线.(程序实现同样用了定序的技巧)

AC代码:

暴力枚举890ms

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=700+5;
struct Point
{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
}p[maxn];
typedef Point Vector;
Vector operator-(Point A,Point B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
double Cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
bool In_Line(Point A,Point B,Point C)//判断3点共线
{
    return fabs(Cross(A-B,A-C))<1e-10;
}


int main()
{
    int n;
    while(scanf("%d",&n)==1 && n)
    {
        for(int i=1;i<=n;++i) scanf("%lf%lf",&p[i].x,&p[i].y);
        int ans=2;
        for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
        {
            int sum=2;
            for(int k=j+1;k<=n;++k)
            if(In_Line(p[i],p[j],p[k])) ++sum;
            ans=max(ans,sum);
        }
        printf("%d\n",ans);
    }
    return 0;
}

排序优化125ms

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=700+5;
const double eps=1e-10;
const double INF=1e20;
int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}
struct Point
{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
}p[maxn];
double get_slope(Point A,Point B)
{
    if(A.x==B.x) return INF;
    else return (A.y-B.y)/(A.x-B.x);
}

int main()
{
    int n;
    while(scanf("%d",&n)==1 && n)
    {
        for(int i=1;i<=n;++i) scanf("%lf%lf",&p[i].x,&p[i].y);
        int ans=2;
        for(int i=1;i<=n;++i)
        {
            int num=0;//保存斜率
            double S[maxn];//保存斜率
            for(int j=i+1;j<=n;++j) S[num++]=get_slope(p[i],p[j]);
            sort(S,S+num);
            int sum=1;//计数相同斜率点的个数
            for(int j=1;j<num;++j)
            {
                if(S[j]==S[j-1]) ++sum;//相同斜率点数加1
                else
                {
                    ans=max(ans,sum+1);//+1是加上枚举的i端点
                    sum=1;
                }
            }
            ans=max(ans,sum+1);//这句不加,无限WA哦
        }
        printf("%d\n",ans);
    }
}