设为首页 加入收藏

TOP

BZOJ5462: [APIO2018] 新家(K-D Tree)
2018-12-06 12:08:21 】 浏览:40
Tags:BZOJ5462: APIO2018 新家 K-D Tree

题意

题目链接

Sol

下面是错误做法,正解请看这里

考虑直接用K-D模拟。。

刚开始想的是维护矩形最大最小值,以及子树中最大圆的位置,然后。。。

实际上最大圆的位置是不用维护的,直接把原序列排一遍序就可以了

再努力卡卡常就过了

如果还过不了的话可以尝试把所有点都转一个角度

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define chmin(x, y) (x = x < y ? x : y)
#define chmax(x, y) (x = x > y ? x : y)
#define ls(x) T[k].ls
#define rs(x) T[k].rs
#define double long double 
const double alpha(acos(-1) / 5);
const double cosa(cos(alpha));
const double sina(sin(alpha));
using namespace std;
const int MAXN = 1e6 + 10;
const double INF = 1e12 + 10, eps = 1e-11;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, WD, root, tot, num, ans[MAXN];
struct Point {
    double x[2], r;
    int id;
    bool operator < (const Point &rhs) const {
        return rhs.x[WD] - x[WD] > eps; 
    }
    double operator [] (const int d) {
        return x[d];
    }
}P[MAXN];
int comp(const Point &a, const Point b) {
    return a.r == b.r ? a.id < b.id : a.r > b.r;
}
struct Node {
    int ls, rs, id;
    double mx[2], mi[2];
    Point p;
}T[MAXN];
void update(int k) {
    for(int i = 0; i <= 1; i++) {
        if(!ans[T[k].id]) T[k].mi[i] = T[k].p[i] - T[k].p.r, T[k].mx[i] = T[k].p[i] + T[k].p.r;
        else T[k].mi[i] = INF, T[k].mx[i] = -INF;
        if(ls(k)) chmin(T[k].mi[i], T[ls(k)].mi[i]), chmax(T[k].mx[i], T[ls(k)].mx[i]);
        if(rs(k)) chmin(T[k].mi[i], T[rs(k)].mi[i]), chmax
		    

(T[k].mx[i], T[rs(k)].mx[i]); } } int Build(int l, int r, int wd) { if(l > r) return 0; WD = wd; int mid = (l + r) >> 1, k = ++tot; nth_element(P + l, P + mid, P + r + 1); T[k].p = P[mid]; T[k].id = P[mid].id; T[k].ls = Build(l, mid - 1, wd ^ 1) ; T[k].rs = Build(mid + 1, r, wd ^ 1); update(k); return k; } double sqr(double x) { return x * x; } bool judge(Point a, Point b) { double tmp = sqr(a[0] - b[0]) + sqr(a[1] - b[1]); return sqr(a.r + b.r) + eps - tmp > 0; } bool pd(int k, Point a) { for(int i = 0; i <= 1; i++) if((a[i] + a.r + eps < T[k].mi[i]) || (a[i] - a.r - eps > T[k].mx[i])) return 1; return 0; } void Delet(int k, Point a) { if(pd(k, a)) return ; if(!ans[T[k].id] && judge(T[k].p, a)) ans[T[k].id] = a.id, T[k].p.r = -INF, num++; if(ls(k)) Delet(ls(k), a); if(rs(k)) Delet(rs(k), a); update(k); } int main() { //freopen("a.in", "r", stdin); N = read(); for(int i = 1; i <= N; i++) { double x = read(), y = read(), tx = x * cosa - y * sina, ty = x * sina + y * cosa; P[i].x[0] = x; P[i].x[1] = y; P[i].r = read(), P[i].id = i; } root = Build(1, N, 0); sort(P + 1, P + N + 1, comp); for(int i = 1; i <= N; i++) if(!ans[P[i].id]) Delet(root, P[i]); for(int i = 1; i <= N; i++) printf("%d ", ans[i]); return 0; }

编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇设置PNG图片DPI 信息,保存为PDF.. 下一篇BZOJ4598: [Sdoi2016]模式字符串(..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }