bzoj 1338: Pku1981 Circle and Points单位圆覆盖

题意：

平面上有$n$个点，问一个半径为$1$的圆最多可以覆盖多少个点。

题解：

最优方案一定有一个点是在圆上的，然后对于其他每个点来说能被覆盖到的角度是一段区间，$O(n)$枚举点后直接$O(nlogn)$线段覆盖即可。

#include <bits/stdc++.h>
using namespace std;

const double pi = 3.1415926535897932384626, eps = 1e-10;
int n, ans;
struct pnt
{
    double x, y;
} a[310];
struct th
{
    double angle;
    int x;
    th(double angle, int x) : angle(angle), x(x) {}
};
vector<th> s;

double dis(pnt x, pnt y)
{
    return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));
}
int cmp(th x, th y)
{
    return abs(x.angle - y.angle) < eps ? x.x > y.x : x.angle < y.angle;
}
int main()
{
    while (1)
    {
        scanf("%d", &n);
        if (n == 0) break;
        for (int i = 1; i <= n; i++)
            scanf("%lf%lf", &a[i].x, &a[i].y);
        ans = 1;
        for (int i = 1; i <= n; i++)
        {
            s.clear();
            for (int j = 1; j <= n; j++)
            {
                if (i == j || dis(a[i], a[j]) > 2) continue;
                // printf("%lf\n", dis(a[i], a[j]));
                double span = acos(dis(a[i], a[j]) / 2), angle = atan2(a[j].y - a[i].y, a[j].x - a[i].x);
                double l = angle - span, r = angle + span;
                if (l < -pi + eps) l += 2 * pi;
                if (r > pi + eps) r -= 2 * pi;
                s.push_back(th(l, 1));
                s.push_back(th(r, -1));
                if (l > r) s.push_back(th(-pi, 1));
            }
            sort(s.begin(), s.end(), cmp);
            int now = 1;
            for (int j = 0; j < s.size(); j++)
            {
                now += s[j].x;
                ans = max(ans, now);
                // printf("%lf %d\n", s[j].angle, s[j].x);
            }
        }
        printf("%d\n", ans);
    }
}