【温州中学】基因光线

题目链接（咕咕咕？）

基因光线

题目描述：

　　黑大帅统治古古怪界后，一直在玩一种很奇葩的游戏。在一个二维平面上，他先复制了\(n\)个小A，把他们放在不同的位置，然后射出一条\(ax+by+c=0\)的基因光线，宽度为\(d\)，即离这条直线的距离不大于\(d\)的小A会被射中。当然，某些悲剧的小A就会被射中，并变成黑小A。当然，这不是重点。玩了很久后，黑大帅猛然发现，自己竟然一次都没有射中小A。黑大帅怒了，于是他开启了作弊模式，将\(c\)改成自己想要的任意数值。现在，黑大帅想知道，在开启了作弊模式后，他射出一道基因光线最多能击中几个小A。

输入格式：

　　第一行五个数字\(a\)，\(b\)，\(d\)，\(n\)，接下来\(n\)行每行两个数字\(x\)，\(y\)表示这个小A的坐标。

输出格式：

　　一行一个数字表示最多能击中几个小A。

样例输入：

1 -1 0.707106782 5
0 0
1 0
0 1
2 0
2 1

样例输出：

4

数据范围：

50%的数据满足\(a=0\);
100%的数据满足\(n<=100000\)，其余所有数值均为绝对值不大于1000的实数。

时间限制：

1s

空间限制：

64M

提示：

remove!!!

题解

射出一条\(ax+by+c=0\)的基因光线?
\(y=-\frac{a}{b}*x-\frac{c}{b}\)
样例输入：\(a\)，\(b\)？
也就是说斜率一定咯O(∩_∩)O~
那么只要随便选取一个直线作为参照，求出每个小A到该直线的距离，使距离差在\(2*d\)范围内能包括的小A数量最大就好了。
点到直线距离公式了解一下：
直线坐标为：\(a*x+b*y+c=0\)
点坐标为：\((x_0,y_0)\)
\[d=\left\vert\frac{a*x_0+b*y_0+c}{\sqrt{a^2+b^2}}\right\vert\]
注意：公式里距离要取绝对值是因为距离一定是非负数，但是我们在这里只是把直线作为一个参照，而不是单纯的距离，有正负之分，所以在计算点的位置时不要用绝对值。
上代码：

#include
using namespace std;
int n;
int ans;
double a,b,d,x,y;
double l[100009];
int main(){scanf("%lf%lf%lf%d",&a,&b,&d,&n);for(int j=1;j<=n;j++){scanf("%lf%lf",&x,&y);l[j]=((a*x+b*y)/sqrt(a*a+b*b));}sort(l+1,l+n+1);int j=1;for(int i=1;i<=n;i++){while(l[i]-l[j]>2*d) j++;ans=max(ans,i-j+1);}printf("%d",ans);return 0;
}

转载于:https://www.cnblogs.com/linjiale/p/11266048.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！