#1421 : 四叉樹
20000ms
2000ms
256MB
描述
小Ho：下個周末我們打算去隔壁城市玩吧？
小Hi：反正來回也挺近的，好啊。
小Ho：那麼我先來規劃一下遊玩路線吧。
小Ho打開了手機中的地圖APP，把坐标移動到了隔壁的城市。各種各樣的店鋪顯示在了街道的地圖上。
小Hi：小Ho，你知道地圖APP是怎麼計算出你周圍的店鋪麼？
小Ho：哎？沒有想過哎。
小Hi：其實這也是個很有意思的問題呢。我們先把模型簡化一下，假設有一張平面圖，上面分布了N個點，第i個點的坐标為(x[i],y[i])。
小Ho：用點來代表店鋪麼？
小Hi：是的，然後假如我們所在的坐标為(a,b)，那麼以我們為中心半徑為r的範圍内(包含邊上)，有多少個點呢？
小Ho：感覺是個很有意思的問題呢，讓我想一想。
提示：四叉樹(Quadtree)
輸入
第1行：2個整數N,M。1≤N≤50,000,0≤M≤5,000。
第2..N+1行：每行2個整數x,y，第i+1行表示第i個點的坐标，保證沒有重複的點。0≤x,y≤30,000
第N+2..N+M+1行：每行3個整數a,b,r，表示詢問的中心坐标(a,b)，以及半徑r。0≤a,b,r≤30,000
輸出
第1..M行：每行1個整數，第i行表示以第i個詢問的(x,y)為中心所包含的點數。
樣例輸入
2 2
1 1
2 2
2 2 1
2 2 2
樣例輸出
1
2
提示：四叉樹(Quadtree)
小Ho：樸素的想法是我用一個二維數組來把整個平面圖表示出來。假設坐标的範圍是L，那麼就需要一個L*L的數組。
對于(a,b)和r，我就檢查a-r到a+r行的b-r列到b+r列，看其中是否存在有點，并且點到(a,b)的距離是小于等于r的。
對于L超過10000的情況就沒有辦法實作了。
小Hi：沒錯，在坐标範圍和點數都很大的情況下，确實會有這樣的問題。
小Ho：我在想能不能把整個區域分割成若幹的小區域，每次都在附近的小區域去找臨近的點呢。
小Hi：小Ho你這個想法很棒，我們不妨來試試吧？
小Ho：那應該怎麼分割呢？
小Hi：你還記得線段樹麼？線上段樹的進行中，我們将一個區間從中點分成兩段。這裡我們也用同樣的方法，将一個區域分割為4塊好了：
從上到下，從左到右，分别标記為1234。
我們将所有的點放進這些區域中，為了讓一個區域中點數不過多，我們設定一個區域的點數上限。
若一個區域的點數過多，我們就将這個區域四分，把新的點放到子區域中去。
小Ho：聽上去好像很有道理。
小Hi：當然有道理了，這種資料結構叫做"四叉樹(Quadtree)"。其每個基本單元為：
QuadtreeNode:
const NODE_CAPACITY; // 每個節點包含的點數限制，常量
boundary; // 該節點的範圍，包含4個參數，區域的上下左右邊界
points; // 該區域内節點的清單
childNode; // 包含4個參數，分别表示4個子區域
假設NODE_CAPACITY=1，那麼我們可以把整個區域分割為：
小Ho：恩，這個我了解了，因為跟線段樹差不多，那麼也就是同樣存在插入和查詢操作了？
小Hi：沒錯。
四叉樹的插入操作：将新的節點(x,y)插入時，若不在目前區域内，退出；否則将其加入該區域的節點清單points，若目前區域的節點清單已經滿了。那麼将該區域進行四分，同時将節點加入子區域中。
insert(QuadtreeNode nowNode, point p):
If (p not in nowNode.boundary) Then
Return
End If
If (nowNode.points.length < NODE_CAPACITY) Then
nowNode.points.append(p)
Else
nowNode.divide() // 将區域四分
For each childNode of nowNode
insert(childNode, p)
End For
End If
四叉樹的查詢操作一般是求一個範圍内的點，是以帶入的參數也是一個區域range：
query(QuadtreeNode nowNode, range):
If (QuadtreeNode.boundary does not intersect range) Then
//該節點的區域與查詢區域不相交
Return empty
End If
For each p in nowNode.points
If (p in range) Then
pointsInRange.append(p)
End For
End For
If (nowNode.isDivide) Then
// 如果該區域有分割過，那麼子區域中的節點也有可能在其中
For each childNode of nowNode
query(childNode, range)
End For
End If
Return pointsInRange
在我們這次的問題中，我們可以用圓的外接正方形作為區域來求得點的清單，再以此檢查是否在圓内。
小Ho：這樣看上去的确搜尋量變少了。
小Hi：沒錯，而且動态建立四叉樹的過程也減少了空間的開銷。
小Ho：恩，我來實作一下試試！
好尴尬-.-在插入點時迷了，迷了，迷了呀---嗚嗚-.-
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int xx[60000],yy[60000];
struct node{
bool fafe;
int length,hao[5],x[2],y[2];
node * clidren[4];
}pp[1000000];
void lon(node *x)
{
x->length=0;
x->fafe=false;
}
int a,b,r,ans,lp,ll;
void pan(int i)//判斷是否在圓中
{
if ((a-xx[i])*(a-xx[i])+(b-yy[i])*(b-yy[i])<=r*r)
ans++;
}
void add(int ii,node * x);
void fen(node * x)
{
int mx=(x->x[0]+x->x[1])>>1;
int my=(x->y[0]+x->y[1])>>1;
for (int i=0;i<4;i++)
x->clidren[i]=&pp[lp++];//一分為四
x->clidren[0]->x[0]=x->x[0];x->clidren[0]->x[1]=mx;
x->clidren[0]->y[0]=x->y[0];x->clidren[0]->y[1]=my;
x->clidren[1]->x[0]=mx+1;x->clidren[1]->x[1]=x->x[1];
x->clidren[1]->y[0]=x->y[0];x->clidren[1]->y[1]=my;
x->clidren[2]->x[0]=x->x[0];x->clidren[2]->x[1]=mx;
x->clidren[2]->y[0]=my+1;x->clidren[2]->y[1]=x->y[1];
x->clidren[3]->x[0]=mx+1;x->clidren[3]->x[1]=x->x[1];
x->clidren[3]->y[0]=my+1;x->clidren[3]->y[1]=x->y[1];
//沒錯
for (int i=0;i<4;i++)
lon(x->clidren[i]);
//沒錯
for (int j=0;j< x->length ;j++)
{
int ii=x->hao[j];
for (int i=0;i<4;i++)
{
if (x->clidren[i]->x[0]<=xx[ii]&&x->clidren[i]->x[1]>=xx[ii]&&x->clidren[i]->y[0]<=yy[ii]&&x->clidren[i]->y[1]>=yy[ii])
{
add(ii,x->clidren[i]);
break;
}
}
}
//沒錯
x->fafe=true;
x->length=0;
//沒錯
}
void add(int ii,node * x)//插入點
{
if (!x->fafe)
{
x->hao[x->length++]=ii;
if (x->length>ll)
{
fen(x);
}
}
else
{
for (int i=0;i<4;i++)
{
if (x->clidren[i]->x[0]<=xx[ii]&&x->clidren[i]->x[1]>=xx[ii]&&x->clidren[i]->y[0]<=yy[ii]&&x->clidren[i]->y[1]>=yy[ii])
{
add(ii,x->clidren[i]);
/*x->clidren[i]->hao[x->clidren[i]->length++]=ii;--開始就是這樣錯的---這個區域可能已經分了呀-.-
if (x->clidren[i]->length>ll)
{
fen(x->clidren[i]);
}*/
break;
}
}
}
}
void query(node * x,int l,int r,int xi,int s)//查找
{
if (!x->fafe)
{
if (x->length)
{
for (int i=0;i<x->length;i++)
pan(x->hao[i]);
}
return ;
}
for (int i=0;i<4;i++)
{
if (l>=x->clidren[i]->x[0]&&r<=x->clidren[i]->x[1]&&xi>=x->clidren[i]->y[0]&&s<=x->clidren[i]->y[1])
{
query(x->clidren[i],l,r,xi,s);
return ;
}
}
if (l>=x->clidren[1]->x[0])
{
query(x->clidren[1],l,r,xi,x->clidren[1]->y[1]);
query(x->clidren[3],l,r,x->clidren[3]->y[0],s);
}
else if (r<=x->clidren[0]->x[1])
{
query(x->clidren[0],l,r,xi,x->clidren[0]->y[1]);
query(x->clidren[2],l,r,x->clidren[2]->y[0],s);
}
else if (xi>=x->clidren[2]->y[0])
{
query(x->clidren[2],l,x->clidren[2]->x[1],xi,s);
query(x->clidren[3],x->clidren[3]->x[0],r,xi,s);
}
else if (s<=x->clidren[0]->y[1])
{
query(x->clidren[0],l,x->clidren[0]->x[1],xi,s);
query(x->clidren[1],x->clidren[1]->x[0],r,xi,s);
}
else
{
query(x->clidren[0],l,x->clidren[0]->x[1],xi,x->clidren[0]->y[1]);
query(x->clidren[1],x->clidren[1]->x[0],r,xi,x->clidren[1]->y[1]);
query(x->clidren[2],l,x->clidren[2]->x[1],x->clidren[2]->y[0],s);
query(x->clidren[3],x->clidren[3]->x[0],r,x->clidren[3]->y[0],s);
}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
pp[0].x[0]=0;pp[0].x[1]=30000;
pp[0].y[0]=0;pp[0].y[1]=30000;
lon(&pp[0]);lp=1;
ll=4;
for (int i=0;i<n;i++)
{
scanf("%d%d",&xx[i],&yy[i]);
add(i,&pp[0]);
}
for (int i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&r);
ans=0;
query(&pp[0],max(0,a-r),min(30000,a+r),max(0,b-r),min(30000,b+r));
printf("%d\n",ans);
}
return 0;
}
/*
2 3
0 1
*/