APIO2018 Circle selection 选圆圈

怼烎@ 2021-12-14 10:45 210阅读 0赞

### APIO2018 Circle selection 选圆圈 ###

#### 题意: ####

[题目传送门][Link 1]

#### 题解： ####

似乎网上题解都是KDTree啊……  
反正似乎裸的KDTree，稍微旋转一下角度，似乎就不会被卡到\\(n^2\\)了……不过如果\\(1e9\\)的\\(double\\)平方一下会爆精，开个\\(long \\ \\ double\\)苟过去……

#### Code： ####

#include <bits/stdc++.h>
    using namespace std;
    const int N = 3e5 + 50;
    #define double long double 
    const double alpha = 1.785;
    const double eps = 1e-4;
    
    int n, nw;
    struct Circle {
      double v[2], r;
      int idx;
      void Read() {
        double x, y;
        scanf("%Lf%Lf%Lf", &x, &y, &r);
        v[0] = x * cos(alpha) + y * sin(alpha);
        v[1] = y * cos(alpha) - x * sin(alpha);
      }
      friend bool operator < (Circle a, Circle b) {
        return a.v[nw] < b.v[nw];
      }
    }p1[N], p2[N], Nw;
    int ret[N];
    
    double Sqr(double x) { return x * x; }
    
    int Check(Circle a, Circle b) {
      return Sqr(a.r + b.r) - Sqr(a.v[0] - b.v[0]) - Sqr(a.v[1] - b.v[1]) >= -eps;
    }
    
    bool Cmp(Circle a, Circle b) {
      return a.r == b.r ? (a.idx < b.idx) : (a.r > b.r);
    }
    
    namespace KDT {
      int ls[N], rs[N];
      double up[N], dn[N], le[N], ri[N];
      int rt;
      void Merge(int x, int y) {
        le[x] = min(le[x], le[y]);
        ri[x] = max(ri[x], ri[y]);
        dn[x] = min(dn[x], dn[y]);
        up[x] = max(up[x], up[y]);
      }
      void Update(int o) {
        le[o] = p1[o].v[0] - p1[o].r; 
        ri[o] = p1[o].v[0] + p1[o].r; 
        dn[o] = p1[o].v[1] - p1[o].r; 
        up[o] = p1[o].v[1] + p1[o].r; 
        if(ls[o]) Merge(o, ls[o]);
        if(rs[o]) Merge(o, rs[o]);
      }
      int Build(int l, int r, int d) {
        if(l > r) return 0;
        if(l == r) return (Update(l), l);
        int mid = (l + r) >> 1; nw = d & 1;
        nth_element(p1 + l, p1 + mid, p1 + r + 1);
        ls[mid] = Build(l, mid - 1, d + 1);
        rs[mid] = Build(mid + 1, r, d + 1);
        Update(mid);
        return mid;
      }
      int In(int o) {
        return le[o] - Nw.v[0] - Nw.r <= eps && Nw.v[0] - Nw.r - ri[o] <= eps && dn[o] - Nw.v[1] - Nw.r <= eps && Nw.v[1] - Nw.r - up[o] <= eps; 
      }
      void Dfs(int o) {
        if(!In(o)) return ;
        if(!ret[p1[o].idx] && Check(Nw, p1[o])) ret[p1[o].idx] = Nw.idx;
        if(ls[o]) Dfs(ls[o]);
        if(rs[o]) Dfs(rs[o]);
      }
    }
    
    int main() {
      scanf("%d", &n);
      for(int i = 1; i <= n; i++) p1[i].Read(), p1[i].idx = i, p2[i] = p1[i];
      sort(p2 + 1, p2 + 1 + n, Cmp);
      KDT::rt = KDT::Build(1, n, 0);
      for(int i = 1; i <= n; i++) {
        if(!ret[p2[i].idx]) {
          Nw = p2[i];
          KDT::Dfs(KDT::rt);
          ret[p2[i].idx] = p2[i].idx;
        }
      }
      for(int i = 1; i <= n; i++) printf("%d ", ret[i]);
      puts("");
      return 0;
    }

转载于:https://www.cnblogs.com/Apocrypha/p/10638682.html

[Link 1]: http://uoj.ac/problem/415