題目大意：給定n個點，求一條直線最多能經過幾個點(n<=1000)

做法：大暴力。。。枚舉每一個點作為直線的端點，然后求出剩下n-1個點和它的斜率，斜率相同的說明可以同時在一條直線上

#include<bits/stdc++.h> #define eps 1e-7 #define N 500005 using namespace std; int n,cnt;double tmp[N*10]; struct Node{int x,y;}p[N]; inline double getk(Node aa,Node bb){return 1.0*(aa.y-bb.y)/(double)(aa.x-bb.x);} int main(){int cas=0;while (scanf("%d",&n)!=EOF){if (n==0) return 0;cnt=0;cas++;int ans1=0;for (int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);for (int i=1;i<n;i++){cnt=0;for (int j=i+1;j<=n;j++){if (p[i].x==p[j].x) tmp[++cnt]=1e9;else tmp[++cnt]=getk(p[i],p[j]);//printf("ID%d %d %.4lf\n",i,j,tmp[cnt]);}sort(tmp+1,tmp+cnt+1);int ans=0;tmp[0]=-1e9;for (int i=1;i<=cnt;i++){if (fabs(tmp[i]-tmp[i-1])>eps){ans=1;ans1=max(ans1,ans);continue;}else ans++,ans1=max(ans1,ans);}}ans1++;if (ans1<4) ans1=0;printf("Photo %d: %d points eliminated\n",cas,ans1);}return 0; }

　　

轉載于:https://www.cnblogs.com/ckr1225/p/8988898.html

總結

以上是生活随笔為你收集整理的CF某gym G的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。