第十三届蓝桥杯省赛A组题解传送门

题目大意

有一根围绕原点$O$顺时针旋转的棒$OA$，初始时指向正上方($Y$轴正向)
在平面中有若干物件，第$i$个物件的坐标为$(x_i,y_i)$，价值为 $z_i$。
当棒扫到某个物件时，棒的长度会瞬间增长$z_i$，且物件瞬间消失(棒的顶端恰好碰到物件也视为扫到)
如果此时增长完的棒又额外碰到了其他物件，也按上述方式消去(它和上述那个点视为同时消失)
如果将物件按照消失的时间排序，则每个物件有一个排名，同时消失的物件排名相同
请输出每个物件的排名，如果物件永远不会消失则输出$-1$
数据保证所有物品坐标两两不同

解题思路

思路上不算很难，但是码量有点大的一道计算几何
首先肯定要极角排序，按照棒旋转的方向对这些点进行排序
排完以后，维护一颗线段树，这颗线段树维护的信息是点到原点的距离的平方的最小值
要这颗线段树有什么用呢？
记棒当前的长度为$len$，棒当前划到的点为$last$
那么棒想划到下一个点的话
就要在$[last+1,n]$这些点里找到从左至右(指区间的左右)第一个到原点的距离的平方小于等于$len^2$的点
如果不存在这样的点
那么就在$[1,last-1]$这些点里试着找到从左至右第一个到原点的距离的平方小于等于$len^2$的点
(相当于在新的一圈里找)
如果还是不存在这样的点，那说明再也找不到能划到的点了，就可以退出死循环了
这个模型即每次返回$[ql,qr]$这段区间里从左至右第一个小于等于$val$的元素的下标，不存在就返回$-1$
学过线段树二分的同学就知道这是模板问题，在$codeforces$也比较常用，复杂度也很优秀只有一个$log$

int search(int id, int l, int r, int ql, int qr, __int128 val) //线段树上二分模板
//返回[ql,qr]这段区间里从左至右第一个小于等于val的元素的下标，不存在就返回-1
{
    if (l == ql && r == qr) //此时的区间正好是询问区间
    {
        if (seg[id].minv > val) //如果整个区间的最小值都大于val，直接返回-1
            return -1;
        else
        {
            if (l == r)
                return l;
            int mid = l + r >> 1;
            if (seg[id << 1].minv <= val) //如果左儿子里有这样的元素，直接进入左儿子即可
                return search(id << 1, l, mid, ql, mid, val);
            else //否则进入右儿子
                return search(id << 1 | 1, mid + 1, r, mid + 1, qr, val);
        }
        return seg[id].minv;
    }
    int mid = l + r >> 1;
    if (qr <= mid)
        return search(id << 1, l, mid, ql, qr, val);
    else if (ql > mid)
        return search(id << 1 | 1, mid + 1, r, ql, qr, val);
    else
    {
        int pos = search(id << 1, l, mid, ql, mid, val);
        if (pos == -1)
            return search(id << 1 | 1, mid + 1, r, mid + 1, qr, val);
        else
            return pos;
    }
}

然后对于每一个扫过的点，我们把它到原点的距离的平方单点修改成无穷大即可，等价于它消失了

change(1, 1, n, idx, INF);

由于数据很大会超过$long\ long$，开了$128$位大整型加快读
如果直接维护距离，不维护距离平方的话可能$long\ long$就够了，但说不定会有精度问题$?$(可以试着写一下)

具体代码

#include <bits/stdc++.h>
typedef long long LL;
const int N = 2e5 + 10;
const __int128 INF = 1e38;
int n, ans[N], idx;
__int128 len;

template <typename T> //快读模板
inline T fastread(T &x)
{
    x = 0;
    T w = 1;
    char ch = 0;
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x = x * w;
}

struct point
{
    LL x, y, z;
    int id;
} a[N];
int Quadrant(point a) //因为棒是顺时针旋转，我们这里把正常意义下的二四象限调换一下
{
    if (a.x >= 0 && a.y > 0)
        return 1;
    if (a.x > 0 && a.y <= 0)
        return 2;
    if (a.x <= 0 && a.y < 0)
        return 3;
    else
        return 4;
}
LL cross(point a, point b) //求叉积
{
    return a.x * b.y - a.y * b.x;
}
bool cmp(point a, point b) //极角排序，排序完后，所有点就按顺时针排好了
{
    if (Quadrant(a) == Quadrant(b))
    {
        if (cross(a, b) == 0) //当极角相同，我们这里按照距离原点距离的平方来排序
            return a.x * a.x + a.y * a.y < b.x * b.x + b.y * b.y;
        return cross(a, b) < 0;
    }
    return Quadrant(a) < Quadrant(b);
}

//线段树
struct
{
    __int128 minv;
} seg[N * 4]; //线段树维护的是点到原点的距离的区间最小值
void pushup(int id)
{
    seg[id].minv = std::min(seg[id << 1].minv, seg[id << 1 | 1].minv);
}
void build(int id, int l, int r)
{
    if (l == r)
        seg[id].minv = a[l].x * a[l].x + a[l].y * a[l].y;
    else
    {
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        pushup(id);
    }
}
void change(int id, int l, int r, int pos, __int128 val)
{
    if (l == r)
        seg[id].minv = val;
    else
    {
        int mid = l + r >> 1;
        if (pos <= mid)
            change(id << 1, l, mid, pos, val);
        else
            change(id << 1 | 1, mid + 1, r, pos, val);
        pushup(id);
    }
}
int search(int id, int l, int r, int ql, int qr, __int128 val) //线段树上二分模板
//返回[ql,qr]这段区间里从左至右第一个小于等于val的元素的下标，不存在就返回-1
{
    if (l == ql && r == qr) //此时的区间正好是询问区间
    {
        if (seg[id].minv > val) //如果整个区间的最小值都大于val，直接返回-1
            return -1;
        else
        {
            if (l == r)
                return l;
            int mid = l + r >> 1;
            if (seg[id << 1].minv <= val) //如果左儿子里有这样的元素，直接进入左儿子即可
                return search(id << 1, l, mid, ql, mid, val);
            else //否则进入右儿子
                return search(id << 1 | 1, mid + 1, r, mid + 1, qr, val);
        }
        return seg[id].minv;
    }
    int mid = l + r >> 1;
    if (qr <= mid)
        return search(id << 1, l, mid, ql, qr, val);
    else if (ql > mid)
        return search(id << 1 | 1, mid + 1, r, ql, qr, val);
    else
    {
        int pos = search(id << 1, l, mid, ql, mid, val);
        if (pos == -1)
            return search(id << 1 | 1, mid + 1, r, mid + 1, qr, val);
        else
            return pos;
    }
}
signed main()
{
    // 注意用了快读就不能关闭流同步，不然大概率会炸
    fastread(n), fastread(len);
    for (int i = 1; i <= n; ++i) //初始化ans数组
        ans[i] = -1;
    for (int i = 1; i <= n; ++i)
    {
        fastread(a[i].x), fastread(a[i].y), fastread(a[i].z);
        a[i].id = i;
    }
    std::sort(a + 1, a + n + 1, cmp);
    build(1, 1, n);
    int last = 0;     // last维护上一个扫到的点
    int rank = 0;     // rank记录扫到点的排名
    int lastrank = 0; // 维护lastrank主要是为了处理有几个点极角相同的特殊情况，根据题意它们的排名相同
    while (true)
    {
        int idx = -1;
        if (last + 1 <= n) //一定要记得这句if
            idx = search(1, 1, n, last + 1, n, len * len);
        if (idx != -1)
            len += a[idx].z;
        else
        {
            if (last >= 2) //一定要记得这句if
                idx = search(1, 1, n, 1, last - 1, len * len);
            if (idx != -1)
                len += a[idx].z;
        }
        if (idx == -1) //没能找到可以划到的点，退出死循环
            break;
        change(1, 1, n, idx, INF); //对于扫过的点，我们可以把它单点修改成无穷大，等价于它消失了
        if (last == 0)
            ans[a[idx].id] = ++rank, lastrank = rank;
        else
        {
            if (Quadrant(a[last]) == Quadrant(a[idx]) && cross(a[last], a[idx]) == 0) //该点和上一个点是同时被扫到的，所以排名要一样
                ans[a[idx].id] = lastrank, ++rank;
            else
                ans[a[idx].id] = ++rank, lastrank = rank;
        }
        last = idx;
    }
    for (int i = 1; i <= n; ++i)
        printf("%d ", ans[i]);
    printf("\n");
    return 0;
}