2010-1146

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

== 题意 ==
魔理沙打妖精，魔炮的形状是二次项系数为a的抛物线，并且可以任意旋转。给定平面上n个妖精的坐标，问最多能打到多少个妖精。

== 题解 ==
规定一个起始的方向，抛物线从这个角度开始扫，转一圈后回到原来的位置。为了方便，这里我们用[-pi, pi]这个范围。对于每个点，求出点进入区域时抛物线的角度和离开区域时抛物线的角度。明显这两个角度是关于轴(0, 0)(x, y)对称的。轴(0, 0)(x,y)的角度alpha=atan2(y, x),则两个角度可以表示成 alpha - delta 和 alpha + delta 的形式。对于delta角，可以解方程x^2^ + y^2^ = (az^2^)^2^ + z^2^，解出z之后，delta = atan(z / (az^2^))。对每个点求出两个角度之后，将所有角度排序，算出初始位置角度等于-pi时，算出初始落在抛物线内点的个数cnt，然后扫一遍排好序的角度，遇到左端点(进入范围)则cnt++，遇到右端点(离开范围)则cnt--，取cnt变化过程中的最大值就是答案。
需要注意的是排序是先按角度排，如果角度相同则左端点排在右端点前面。头尾的情况很容易出错也需要特别注意。

== 代码 ==

{{{
#!cpp
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#define PI acos(-1.0)
#define MAXN 30005
#define EPS 1e-8
using namespace std;
double x[MAXN], y[MAXN];
bool cmp(pair<double, int> p1, pair<double, int> p2) {
    if(!(abs(p1.first - p2. first) < EPS))
        return p1.first < p2.first;
    else
        return p1.second > p2.second;
}
int main() {
    int n;
    double a;
    while(scanf("%d%lf", &n, &a) != EOF) {
        double tx, ty, c, r, alpha, delta, le, ri;
        vector<pair<double, int> > vp;
        for(int i = 0; i < n; ++i) {
            scanf("%lf", &x[i]);
        }
        for(int i = 0; i < n; ++i) {
            scanf("%lf", &y[i]);
        }
        int cnt = 0;
        for(int i = 0; i < n; ++i) {
            tx = x[i];
            ty = y[i];
            c = -tx * tx - ty * ty;
            r = (-1 + sqrt(1 - 4 * a * a * c)) / (2 * a * a);
            r = sqrt(r);
            alpha = atan2(ty, tx);
            delta = atan(1.0 / (a * r));
            le = alpha - delta, ri = alpha + delta;
            if(le < -PI)
                le += 2 * PI;
            if(ri > PI)
                ri -= 2 * PI;
            if(le > ri)
                ++cnt;
            vp.push_back(make_pair(le, 1));
            vp.push_back(make_pair(ri, -1));
        }
        sort(vp.begin(), vp.end(), cmp);
        int maxcnt = cnt;
        vector<pair<double, int> >::iterator it;
        for(it = vp.begin(); it != vp.end(); ++it) {
            cnt += it->second;
            if(cnt > maxcnt)
                maxcnt = cnt;
        }
        printf("%d daze\n", maxcnt);
    }
    return 0;
}
}}}

题意

魔理沙打妖精，魔炮的形状是二次项系数为a的抛物线，并且可以任意旋转。给定平面上n个妖精的坐标，问最多能打到多少个妖精。

题解

规定一个起始的方向，抛物线从这个角度开始扫，转一圈后回到原来的位置。为了方便，这里我们用[-pi, pi]这个范围。对于每个点，求出点进入区域时抛物线的角度和离开区域时抛物线的角度。明显这两个角度是关于轴(0, 0)(x, y)对称的。轴(0, 0)(x,y)的角度alpha=atan2(y, x),则两个角度可以表示成 alpha - delta 和 alpha + delta 的形式。对于delta角，可以解方程x² + y² = (az²)² + z²，解出z之后，delta = atan(z / (az²))。对每个点求出两个角度之后，将所有角度排序，算出初始位置角度等于-pi时，算出初始落在抛物线内点的个数cnt，然后扫一遍排好序的角度，遇到左端点(进入范围)则cnt++，遇到右端点(离开范围)则cnt--，取cnt变化过程中的最大值就是答案。

需要注意的是排序是先按角度排，如果角度相同则左端点排在右端点前面。头尾的情况很容易出错也需要特别注意。

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#define PI acos(-1.0)
#define MAXN 30005
#define EPS 1e-8
using namespace std;
double x[MAXN], y[MAXN];
bool cmp(pair<double, int> p1, pair<double, int> p2) {
    if(!(abs(p1.first - p2. first) < EPS))
        return p1.first < p2.first;
    else
        return p1.second > p2.second;
}
int main() {
    int n;
    double a;
    while(scanf("%d%lf", &n, &a) != EOF) {
        double tx, ty, c, r, alpha, delta, le, ri;
        vector<pair<double, int> > vp;
        for(int i = 0; i < n; ++i) {
            scanf("%lf", &x[i]);
        }
        for(int i = 0; i < n; ++i) {
            scanf("%lf", &y[i]);
        }
        int cnt = 0;
        for(int i = 0; i < n; ++i) {
            tx = x[i];
            ty = y[i];
            c = -tx * tx - ty * ty;
            r = (-1 + sqrt(1 - 4 * a * a * c)) / (2 * a * a);
            r = sqrt(r);
            alpha = atan2(ty, tx);
            delta = atan(1.0 / (a * r));
            le = alpha - delta, ri = alpha + delta;
            if(le < -PI)
                le += 2 * PI;
            if(ri > PI)
                ri -= 2 * PI;
            if(le > ri)
                ++cnt;
            vp.push_back(make_pair(le, 1));
            vp.push_back(make_pair(ri, -1));
        }
        sort(vp.begin(), vp.end(), cmp);
        int maxcnt = cnt;
        vector<pair<double, int> >::iterator it;
        for(it = vp.begin(); it != vp.end(); ++it) {
            cnt += it->second;
            if(cnt > maxcnt)
                maxcnt = cnt;
        }
        printf("%d daze\n", maxcnt);
    }
    return 0;
}