最近點對-分治

題序

給平片上相異

$N$點

$(x_1,y_1),(x_2,y_2),...,(x_N,y_n)$
請計算最近點對的距離的平方
也就是找出

$i,j$，滿足

$1\le i<j\le N$，且

$(x_i-x_j{)}^2+(y_i-y_j{)}^2$為最小

輸入說明：
第一行包含一個正整數

$N$，代表平面上的點數。
接下來

$N$行，每行包含兩整樹

$x_i,y_i$代表第

$i$個點的座標

$1\le N\le 2\times {10}^5$

$-{10}^9\le x_i,y_i\le {10}^9$

$(x_i,y_i)\ne (x_j,y_j)\ne j$，不存在兩點座標相同

輸出說明：
輸出正整數，代表最近點對的距離的平方

範例輸入
4
1 3
7 5
-4 9
2 -5

範例輸出
40

題解

這題我是用分治的想法來做，我們可以利用排序找出中點，把點分成左右兩邊
分出兩個子問題，而最近點對只有三種可能
1.左邊區域的最近點對

$(dl)$
2.右邊區域的最近點對

$(dr)$
3.一個點在左區域，一個點在右區域的最近點對
1、2、3之中的最小值就是答案
1和2的值都會在遞迴的過程中被傳上來，所以我們只剩下3要怎麼求
我們先定義

$d=min(dl,dr)$
我們可以知道3的點只可能會出現在中點向左右展開

$d$的空間中
並且我們可以將空間中所有點都用點的

$y$座標來排序
並且從每個點向上枚舉看可不可以形成最近點對
當枚舉到兩點距離

$>d$時就

$break$優化複雜度

但這個方法你可能會想，每次枚舉的區域內有沒有可能存在大量的點導致複雜度大增呢
如果我們仔細想一想會發現對每一次枚舉的點

$P$來說，這個空間中的點是常數個
我們是從下向上枚舉(從

$y$小的開始)
而有可能和

$P$點成為最近點對的範圍就只有點向左、右、上擴張

$d$，
形成一個

$2d\times d$的矩形空間
我們將這個空間分成2等分的正方形，在每一個正方形中長為

$d$寬為

$d$
根據畢氏定理，對角線為

$\sqrt{2}d$，所以我們可以得知每個正方形內最多只有一個點
根據鴿籠原理，若我們放超過2個點(不包含

$P$)，必會有一個小矩形有兩個點，且這兩點的距離小於

$d$
和前的

$d$計算矛盾，故可知最多只有2個點(不包含

$P$)

時間複雜度分析

每一層都需要對y進行排序，時機複雜度

$O(nlogn)$，每次遞迴都將

$n/2$共

$logn$層，時間複雜度

$O(logn)$
總時間複雜度

$O(nlo{g}^{2}n)$

實作

$O(nlo{g}^{2}n)$

#include<bits/stdc++.h>
#define LL long long int
#define INF 9223372036854775807
#define x first
#define y second
using namespace std;
LL n;
pair<LL,LL> tmp[200001];
vector<pair<LL,LL>> p;

LL dis(pair<LL,LL> a,pair<LL,LL> b){
    LL dx = a.x - b.x , dy = a.y - b.y;
    return dx * dx + dy * dy;
}

bool cmp(pair<LL,LL> a,pair<LL,LL> b){
    return a.y < b.y;
}
#define mid (l + r) / 2
LL divide(LL l,LL r){
    if(l == r)return INF;
	LL m = (l + r) / 2;	
	LL ans = min(divide(l,mid),divide(mid+1,r));
	LL midval =p[m].x;
	LL pp = -1;

    for(LL i = l; i <= r;i++){
    	if((midval - p[i].x) *(midval - p[i].x) <= ans){
            tmp[++pp] = p[i];
        }
    }
    sort(tmp,tmp+pp+1,cmp);
    
    for(LL i = 0; i < pp+ 1; i++){
        for(LL j = i + 1; j < pp + 1;j++){
            ans = min(ans,dis(tmp[i],tmp[j]));
            if((tmp[i].y-tmp[j].y)*(tmp[i].y-tmp[j].y) > ans)break;
        } 
/*下面這兩種也都是對的
    	for(LL j = i + 1; j < pp + 1;j++){
            ans = min(ans,dis(tmp[i],tmp[j]));
            if(dis(tmp[i],tmp[j]) > ans)break;
        } 
*/
/*     
        for(LL j = i + 1; j < min(i + 3 , pp+1);j++){
            ans = min(ans, dis(tmp[i],tmp[j]));  
        }
*/
      }
    return ans;
}
#undef mid
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;

    p.assign(n,{0,0});
	for(int i = 0; i < n; i++){
		cin >> p[i].x;
		cin >> p[i].y;
	}
	sort(p.begin(),p.end());
	cout << divide(0,n - 1) <<'\n';
	return 0;
}

題解

$O(nlogn)$

點擊連結以繼續觀看
https://hackmd.io/@samson-note/ry5i3l4La

題解-隨機算法

點擊連結以繼續觀看
https://hackmd.io/@samson-note/ry5i3l4La