APIO2018 Circle selection 选圆圈
题意:
题目传送门
题解：
似乎网上题解都是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
相关资源：JAVA上百实例源码以及开源项目
