POJ 求平面点阵中的最大共线点数系列（POJ 1118 + 2606 + 2780）

三道题用的一个代码，，，水过了。

题意都是：给出平面若干个点的坐标，求共线的点的最多的点的数目。即在同一条直线的上的最多的点数目。

解题思路是：求出两两坐标的两点间的斜率，然后一次比较斜率，相同的则共线，求出最大的共线数，输出即可。

（或者可以用三个点共线的做，其实质依然是靠斜率来判断是否共线）。

代码如下（两点斜率）：

[cpp] view plaincopyprint 在CODE上查看代码片派生到我的代码片

/***** 简单ACM水题 ********/

/******** written by C_SuooL_Hu ************/

////////////////直线与点///////////////

////////////////POJ_1118_2606_2780///////////////

/****************************************************************************/

题目大意：给出平面上若干点，求属于同一条的直线的最多点数。

思路：分别求出其中一点与其它点的直线的斜率，进行排序，如果斜率相同则同一条直线。

/****************************************************************************/

#include

using namespace std;

const double INF=210000000;

struct point

{

int x,y;

};

int cmp(const void *a ,const void *b)

{

if( *(double*)a> *(double *)b)

return 1;

else

return -1;

}

point p[1010];

double k[1010];

int main()

{

// freopen("in.txt","r",stdin);

// freopen("out.txt","w",stdout);

int N, i, j, l, counter, ans;

while(cin >> N && N)

{

for(i=0;i

cin >> p[i].x >

> p[i].y ;

ans = 0;

for(i=0;i

{

for(j=i+1,l=0;j

{

if(p[i].x==p[j].x)

k[l]=INF;

else

k[l]=double(p[i].y-p[j].y)/(p[i].x-p[j].x);

}

qsort(k,l,sizeof(k[0]),cmp);

for(j=0;j

{

counter=1;

while(j+1

{

j++;

counter++;

}

if(counter>ans)

ans=counter;

}

printf("%d\n",ans+1);

}

return 0 ;

}

代码二（三点共线）：

#include   
#include   
#include   
using namespace std;  
const int maxn=202;  
struct point  
{  
    int x;  
    int y;  
} pnt[maxn];  
int main()  
{  
    //freopen("in.txt","r",stdin);  
    int n, max, cnt, i, j, k;  
    while(cin >> n)  
    {  
        memset(pnt,0,sizeof(pnt));  
        for(i=0;i> pnt[i].x >> pnt[i].y;  
        }  
        max=0;  
        for(i=0;imax)max=cnt;  
            }  
        }  
        cout << max+2 << endl;  
    }  
    return 0;  
}

POJ 求平面点阵中的最大共线点数系列 （POJ 1118 + 2606 + 2780）