luogu4631 [APIO2018] Circle selection 选圆圈

题目描述

在平面上,有 $n$个圆,记为 $c_1, c_2,...,c_n$ 。我们尝试对这些圆运行这个算法:

  1. 找到这些圆中半径最大的。如果有多个半径最大的圆,选择编号最小的。记为 $c_i$。

  2. 删除 $c_i$及与其有交集的所有圆。两个圆有交集当且仅当平面上存在一个点,这个点同时在这两个圆的圆周上或圆内。(原文直译:如果平面上存在一个点被这两个圆所包含,我们称这两个圆有交集。一个点被一个圆包含,当且仅当它位于圆内或圆周上。)

  3. 重复上面两个步骤直到所有的圆都被删除。

当 $c_i$被删除时,若循环中第 $1$步选择的圆是 $c_j$,我们说 $c_i$被 $c_j$删除。对于每个圆,求出它是被哪一个圆删除的。

输入格式

第一行包含一个整数 $n$,表示开始时平面上圆的数量 $(1 ≤ n ≤ 3 × 10^5)$。

接下来 $n$行 , 每行包含三个整数 $x_i, y_i, r_i$ 依次描述圆 $c_i$圆心的 $x$坐标、$y$坐标和它的半径$(-10^9 ≤ x_i, y_i ≤ 10^9, 1 ≤ r_i ≤ 10^9)$。

输出格式

输出一行,包含 $n$个整数 $a_1, a_2, ..., a_n$,其中 $a_i$表示圆 $c_i$是被圆 $c_{a_i}$删除的。

样例输入

11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1

样例输出

7 2 7 4 5 6 7 7 4 7 6

说明

$n \leq 3 × 10^5$


分析

当时APIO考到这题时完全没思路……此题正解很迷,不过高分暴力很可做。

平面上的问题要暴力搞的话可以想到kdtree。如果是矩形的话比较好做,很容易判断一个节点是否和一个矩形相离。不过如果矩形改成圆的话就不好判相离。

不过因为我们打的是暴力数据结构,判相离的目的是剪枝,而剪枝可以不一定剪得那么细。所以我们可以把圆扩大成正方形,按矩形的方法判相离即可。

复杂度玄学,洛谷数据可过。如果把所有点旋转一个角度也许效果更好。

代码

#include <bits/stdc++.h>
typedef long long ll;

const int N = 3e5+50;
const int INF = 0x3f3f3f3f;

int n;
int cur;

struct Circle {
    int pos[2], r, id;

    bool operator < (const Circle &t) const {
        return pos[cur] < t.pos[cur];
    }
} c[N];

struct Node {
    int ch[2];
    Circle c;
    int mi[2], mx[2];
} tr[N];

int top, rt;
int ans[N];

void pushUp(int u) {
    int ls = tr[u].ch[0], rs = tr[u].ch[1];
    int r = tr[u].c.r;
    for (int d = 0; d < 2; d++) {
        tr[u].mi[d] = std::min(tr[u].c.pos[d] - r, std::min(tr[ls].mi[d], tr[rs].mi[d]));
        tr[u].mx[d] = std::max(tr[u].c.pos[d] + r, std::max(tr[ls].mx[d], tr[rs].mx[d]));
    }
}

void build(int &u, int L, int R, int d) {
    if (L > R) return;
    int mid = L + R >> 1;
    cur = d;
    std::nth_element(c+L, c+mid, c+R+1);
    tr[u=mid].c = c[mid];
    build(tr[u].ch[0], L, mid-1, d^1);
    build(tr[u].ch[1], mid+1, R, d^1);
    pushUp(u);
}

bool cmp(const Circle &t1, const Circle &t2) {
    return t1.r > t2.r || t1.r == t2.r && t1.id < t2.id;
}

bool allOut(const Node &u, const Circle &c) {
    if (u.mx[0] < c.pos[0] - c.r) return true;
    if (u.mi[0] > c.pos[0] + c.r) return true;
    if (u.mx[1] < c.pos[1] - c.r) return true;
    if (u.mi[1] > c.pos[1] + c.r) return true;
    return false;
}

ll sqr(int x) {
    return (ll)x * x;
}

bool check(const Circle &c1, const Circle &c2) {
    return sqr(c1.pos[0]-c2.pos[0]) + sqr(c1.pos[1]-c2.pos[1]) <= sqr(c1.r+c2.r);
}

void query(int u, const Circle &c) {
    if (allOut(tr[u], c)) return;
    if (!ans[tr[u].c.id] && check(c, tr[u].c))
        ans[tr[u].c.id] = c.id;
    query(tr[u].ch[0], c);
    query(tr[u].ch[1], c);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &c[i].pos[0], &c[i].pos[1], &c[i].r);
        c[i].id = i;
    }
    for (int d = 0; d < 2; d++) {
        tr[0].mi[d] = INF;
        tr[0].mx[d] = -INF;
    }
    build(rt, 1, n, 0);
    std::sort(c+1, c+n+1, cmp);
    for (int i = 1; i <= n; i++) {
        if (!ans[c[i].id])
            query(rt, c[i]);
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", ans[i]);
    puts("");
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论