POJ1106极角排序

71 阅读 0 评论 47 点赞

我是靠谱客的博主机灵自行车，最近开发中收集的这篇文章主要介绍POJ1106极角排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目

POJ Transmitters

给出若干个点和一个半圆，半圆可以绕着圆心任意旋转，问最多能覆盖多少个点。

解题思路

距离圆心的距离大于半径的点可以直接先排除掉。

将剩余的点进行极角排序，然后用一个双端队列维护能被半圆覆盖的点，当队首和当前处理点的角度大于 $π$ 时，弹出队首元素。期间队列最大的size就是答案。

需要注意的是，当前处理点极角接近 $π$ 时，最开始邻近 $- π$ 处的点也会有贡献，可以将所有点复制一份加到后面，并将复制的点极角加上 $2 π$ 。

时间复杂度 $O (n l o g n)$ 。比网上的很多题解更优。

代码

~~G++死活过不去~~

#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
const long double PI = acos(-1.0);
const int N = 1e5 + 5;
const long double eps = 1e-6;
struct node
{
    int x, y;
    long double theta;
    int id;
    bool operator<(const node temp) const
    {
        return theta < temp.theta;
    }
} s[N];
int X, Y;
long double R;
void solve()
{
    int n;
    scanf("%d", &n);
    int m = 0;
    for (int i = 1; i <= n; i++)
    {
        int tx, ty;
        scanf("%d %d", &tx, &ty);
        tx -= X;
        ty -= Y;
        if ((tx * tx) + (ty * ty) <= R * R)
            s[++m].x = tx, s[m].y = ty, s[m].theta = atan2((long double)s[m].y, (long double)s[m].x);
    }
    sort(s + 1, s + 1 + m);
    for (int i = 1; i <= m; i++)
    {
        s[i].id = i;
        s[i + m] = s[i];
        s[i + m].theta += 2 * PI;
    }
    m *= 2;
    deque<node> q;
    int ans = 0;
    for (int i = 1; i <= m; i++)
    {
        if (!q.size())
        {
            q.push_back(s[i]);
            ans = max(ans, (int)q.size());
            continue;
        }
        while (q.size() && (q.front().theta + PI + eps < s[i].theta))
            q.pop_front();
        q.push_back(s[i]);
        ans = max(ans, (int)q.size());
    }
    printf("%dn", ans);
}
int main()
{
    while (~scanf("%d %d %Lf", &X, &Y, &R) && R > 0)
        solve();
    return 0;
}