題意：給你n個(gè)點(diǎn)的坐標(biāo)。求一條直線(xiàn)最多能穿過(guò)多少個(gè)點(diǎn)。
思路：枚舉(n^2)+求斜率+排序 （復(fù)雜度n^2logn）大功告成

//By: Sirius_Ren #include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n,maxx;double s[705]; struct line{int x,y;}a[705]; bool cmp(line a,line b){return a.x<b.x;} int main() {while(scanf("%d",&n)&&n){maxx=0;for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);sort(a+1,a+1+n,cmp);for(int i=1;i<n;i++){int tot=1,ans=0;for(int j=i+1;j<=n;j++)s[tot++]=(1.0*a[j].y-1.0*a[i].y)/(1.0*a[j].x-1.0*a[i].x);sort(s+1,s+tot);for(int i=1;i<tot-1;i++)if(fabs(s[i+1]-s[i])<1e-6)ans++,maxx=max(maxx,ans);else ans=0;}printf("%d\n",maxx+2);} }

轉(zhuǎn)載于:https://www.cnblogs.com/SiriusRen/p/6532470.html

總結(jié)

以上是生活随笔為你收集整理的POJ 1118 求平面上最多x点共线的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。