最多几个点在一条直线上
思路:判断每一点与其他多少个点在一条直线上,记录在一条直线上的最大点数。
#include <iostream> #include <algorithm> using namespace std; #define MAX 10010 #define INF 2100000000 double K[MAX]; struct Node { int x, y; }; Node N[MAX]; int main() { int n, i, j,c, ant; while (cin>> n && n) { for (i=0; i<n; i++) cin>>N[i].x>>N[i].y; ant = 0; for (i=0; i<n; i++) { for (j=i+1, c=0; j<n; j++, c++) { if (N[i].x==N[j].x) K[c] = INF; else K[c] = double(N[i].y-N[j].y)/(N[i].x-N[j].x); } sort(K, K+c); for (j=0; j<c; j++)//判断c个点中斜率相同的点中,相同点数的最多点是多少点 { int count = 1; while (j+1<c && K[j]==K[j+1])//判断(i, j)与(i, j+1)的斜率是否相同 { j++; count++; } if (count>ant) ant = count; } } cout<<ant+1<<endl; } return 0; }