基因光线
基因光线
黑大帅统治古古怪界后，一直在玩一种很奇葩的游戏。在一个二维平面上，他先复制了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!!! 容易计算得在y轴上相差的距离为d*c，c见程序。我们先手动忽略常数，然后计算出该光线刚好击中一点时的 y值，然后扩展d的时候把每条光线都向上移d，就转化为对于每个2*d的区间求最多并集个数。即可 #include #include #include #include #include using namespace std; #define PER(i,a,b) for(int i=a;i<=b;i++) #define REP(i,a,b) for(int i=a;i>=b;i--) double a,b,d; int n; struct NODE{ double x,y; }l[1100001]; const double inf=0.000000003; double ll[1100001]; double rr[1100001]; double c; void prepare( int x) { ll[x]=l[x].x*a+l[x].y*b; } int pointl,pointr; int ans=0; int ond=0; int main() { cin>>a>>b>>d>>n; PER(i,1,n) scanf ( "%lf%lf" ,&l[i].x,&l[i].y); c= sqrt (a*a+b*b); d=d*c; PER(i,1,n) prepare(i); sort(ll+1,ll+n+1); int s=0; int e=1; while (e { s++; while (ll[e+1]-ll[s]<=d*2&&e ans=max(ans,e-s+1); } cout< "\n" ; }
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
