# 最近點對-分治

## 題序
給平片上相異$N$點$(x_1,y_1),(x_2,y_2),...,(x_N,y_n)$
請計算最近點對的距離的平方
也就是找出$i,j$，滿足$1≤i<j≤N$，且$(x_i-x_j)^2+(y_i-y_j)^2$為最小

輸入說明：
第一行包含一個正整數$N$，代表平面上的點數。
接下來$N$行，每行包含兩整樹$x_i,y_i$代表第$i$個點的座標
$1≤N≤2×10^5$
$-10^9≤x_i,y_i≤10^9$
$(x_i,y_i)≠(x_j,y_j)≠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×d$的矩形空間
我們將這個空間分成2等分的正方形，在每一個正方形中長為$d$寬為$d$
根據畢氏定理，對角線為$\sqrt2d$，所以我們可以得知每個正方形內最多只有一個點
根據鴿籠原理，若我們放超過2個點(不包含$P$)，必會有一個小矩形有兩個點，且這兩點的距離小於$d$
和前的$d$計算矛盾，故可知最多只有2個點(不包含$P$)
## 時間複雜度分析
每一層都需要對y進行排序，時機複雜度$O(nlogn)$，每次遞迴都將$n/2$共$logn$層，時間複雜度$O(logn)$
總時間複雜度$O(nlog^2n)$
## 實作$O(nlog^2n)$

#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