标签：cross cond div etc math 直接 排序 ros 判断
「APIO2018」选圆圈(K-D Tree/CDQ+Set)
Part1 K-D Tree做法
K-D Tree经常用来优化大暴力。。
把圆\((x,y,r)\)视为矩形\((x-r,y-r,x+r,y+r)\)，依据\((x,y)\)构建K-D Tree
维护K-D Tree每个节点所有矩形最小和最大的\(x,y\)，通过判断当前圆与其是否有交来剪枝
删去的节点\(x,y\)不算进矩形范围即可
很显然这是一个最坏\(O(n^2)\)的算法，直接\(x,y\)轮换建树这样写APIO的数据已经卡过了。。
比较好的办法是按照\(x,y\)的方差大的一维建树，当然旋转角度也是可以的
实际运行速度堪比\(O(n\log n)\)
Code1:旋转+\(x,y\)轮换建树
#include
using namespace std;
typedef long long ll;
typedef long double db;
#define rep(i,a,b) for(int i=a,i##end=b;i=i##end;--i)
template inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template inline void cmax(T &a,T b){ ((ar) return 0;
int u=(l+r)>>1;
nth_element(B+l,B+u,B+r+1,cmp);
typ^=1; ch[u][0]=Build(l,u-1),ch[u][1]=Build(u+1,r); typ^=1;
return Up(u),u;
}
int Cross(int x,Node y){
if(lx[x]>rx[x]) return 0;
if(In(lx[x],ly[x],y) || In(lx[x],ry[x],y) || In(rx[x],ly[x],y) || In(rx[x],ry[x],y)) return 1;
if(lx[x]-epsy.r:x.id
\[\
\]
Code2:方差建树
#include
using namespace std;
using ll=long long;
#define rep(i,a,b) for(int i=a,i##end=b;i=i##end;--i)
template inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template inline void cmax(T &a,T b){ ((ay;
}
int Build(int l,int r) {
if(l>r) return 0;
int u=(l+r)>>1;
typ=Get(l,r),nth_element(B+l,B+u,B+r+1,cmp);
ch[u][0]=Build(l,u-1),ch[u][1]=Build(u+1,r);
return Up(u),u;
}
int Cross(int x,Node y){
if(lx[x]>rx[x]) return 0;
if(In(lx[x],ly[x],y) || In(lx[x],ry[x],y) || In(rx[x],ly[x],y) || In(rx[x],ry[x],y)) return 1;
if(lx[x]y.r:x.id
\[\
\]
Part2 CDQ+Set
这是一个稳定\(O(n\log ^2n)\)的算法
按照\(r\)递减，\(id\)递增的顺序对于圆排序后，\(CDQ\)考虑\([l,mid]\)对\([mid+1,r]\)的贡献
先处理\([l,mid]\)的部分，就能知道哪些圆可以对\([mid+1,r]\)产生贡献
处理贡献时，依然把圆视为矩形，按照\(x\)插入、删除和查询矩形的左右边界\((x-r,y),(x+r,y)\)
插入、删除和查询均是在\(set\)中维护\(y\)的前驱后继
同时还需要交换\(x,y\)重新进行一遍
正确性：
与每个圆交的圆一定在\(x\)或\(y\)上与它相邻
如果这个圆在x,y上都不与它相邻还与它相交，则必然会跨过一个相邻的圆，这个圆不会被加入set
故不存在这种情况
实际运行常数很大，被K-D Tree吊起来打
#include
using namespace std;
#define rep(i,a,b) for(i=a;i;
#define M make_pair
#define X first
#define Y second
#define S(x) 1ll*(x)*(x)
const int N=1e6+10;
int n,c[N],i,j,D[N];
struct C{ int x,y,r,i; } A[N];
void Upd(int i,int j) { if(S(A[i].x-A[j].x)+S(A[i].y-A[j].y)i) c[A[j].i]=A[i].i; }
setst;
P I[N],E[N],Q[N];
void Work(int l,int r){
int mid=(l+r)>>1,n=0,m=0,x=0,y=0,t;
rep(i,l,mid) if(c[A[i].i]==A[i].i) I[m]=M(A[i].x-A[i].r,i),E[m++]=M(A[i].x+A[i].r+1,i);
rep(i,mid+1,r) Q[n++]=M(A[i].x-A[i].r,i),Q[n++]=M(A[i].x+A[i].r,i);
sort(I,I+m),sort(E,E+m),sort(Q,Q+n),st.clear();
rep(i,0,n-1) {
while(xY,t);
if(j!=st.begin()) Upd((--j)->Y,t);
}
}
void Solve(int l,int r) {
if(r-l+1>1;
Solve(l,mid);
Work(l,r);rep(i,l,r) swap(A[i].x,A[i].y);
Work(l,r);rep(i,l,r) swap(A[i].x,A[i].y);
Solve(mid+1,r);
}
int main(){
scanf("%d",&n);
rep(i,1,n) scanf("%d%d%d",&A[i].x,&A[i].y,&A[i].r),A[i].i=i;
sort(A+1,A+n+1,[&](C x,C y){return M(-x.r,x.i)
「APIO2018」选圆圈(K-D Tree/CDQ+Set)
标签：cross cond div etc math 直接 排序 ros 判断
原文地址：https://www.cnblogs.com/chasedeath/p/13379813.html