題目描述

“我該怎么辦？”飛行員klux向你求助。

事實上，klux面對的是一個很簡單的問題，但是他實在太菜了。

klux要想轟炸某個區(qū)域內(nèi)的一些地方，它們是位于平面上的一些點，但是（顯然地）klux遇到了抵抗，所以klux只能飛一次，而且由于飛機比較破，一點起飛就只能沿直線飛行，無法轉(zhuǎn)彎。現(xiàn)在他想一次轟炸最多的地方。

輸入輸出格式

輸入格式：

第一行為n

輸入數(shù)據(jù)由n對整數(shù)組成(1<=n<=700)，每對整數(shù)表示一個點的坐標(biāo)。沒有一個點會出現(xiàn)兩次。

輸出格式：

一個整數(shù)，表示一條直線能覆蓋的最多的點數(shù)。

輸入輸出樣例

輸入樣例#1：
5 1 1 2 2 3 3 9 10 10 11 輸出樣例#1：
3

說明

本題翻譯并改編自uva270，數(shù)據(jù)及解答由uva提供。

思路：

暴力枚舉。

一般式：a*x+b*x+c==0,

∵a*x[i]+b*y[i]+c=a*x[j]+b*y[j]+c=0;

∴a:b=(y[j]-y[i]):(x[i]-x[j]);

∴a=y[j]-y[i],b=x[i]-x[j],c=-a*x[i]-b*y[i].

代碼實現(xiàn)：

1 #include<cstdio> 2 int n,a,b,c,x[710],y[710],now,ans; 3 int main(){ 4 scanf("%d",&n); 5 for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]); 6 for(int i=1;i<n;i++) 7 for(int j=i+1;j<=n;j++){ 8 a=y[j]-y[i];b=x[j]-x[i];c=-a*x[i]+b*y[i];now=0; 9 for(int k=1;k<=n;k++) if(a*x[k]-b*y[k]+c==0) ++now; 10 if(now>ans) ans=now; 11 } 12 printf("%d\n",ans); 13 return 0; 14 }

數(shù)學(xué)不好。

題目來源：洛谷

轉(zhuǎn)載于:https://www.cnblogs.com/J-william/p/6295779.html

總結(jié)

以上是生活随笔為你收集整理的轰炸的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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