“我该怎么办?”飞行员klux向你求助。
事实上,klux面对的是一个很简单的问题,但是他实在太菜了。
klux要想轰炸某个区域内的一些地方,它们是位于平面上的一些点,但是(显然地)klux遇到了抵抗,所以klux只能飞一次,而且由于飞机比较破,一点起飞就只能沿直线飞行,无法转弯。现在他想一次轰炸最多的地方。
input:
输入数据由n对整数组成(1<n<700),每对整数表示一个点的坐标。没有一个点会出现两次。
output:
一个整数,表示一条直线能覆盖的最多的点数。
input:
5
1 1
2 2
3 3
9 10
10 11
output:
3
分析:
简单的计算几何题目,利用了直线方程式(同一直线上任意点都满足方程式)
直线的方程我们先看看两点式方程:
(y-y1)/(y2-y1)=(x-x1)/(x2-x1)
交叉相乘并整理可以得到:(y-y1)(x2-x1)=(y2-y1)(x-x1)
化为一般式:ax+by+c=0 得:
其中:
A=y2-y1
B=x2-x1
C=-ax1+by1
这样就可以尽量避免除法,因为众所周知,除法是很费时间的,而且有精度问题。
再一次枚举n个点,找出最多。
【参考程序】:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
struct point
{
int x,y;
};
point p[710];
int n,i,j,max,ans;
int main()
{
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
ans=0;
for (i=1;i<=n-1;i++)
for (j=i+1;j<=n;j++)
{
max=0;
int a,b,c;
a=p[j].y-p[i].y;
b=p[j].x-p[i].x;
c=-a*p[i].x+b*p[i].y;
for (int k=1;k<=n;k++)
if (a*p[k].x-b*p[k].y+c==0)
max++;
if (ans<max) ans=max;
}
printf("%d\n",ans);
system("pause");
return 0;
}