【ABC409】F問題 - Connecting Points　考察から実装(c++)まで

AtCoderBeginnerContest409の解説＆感想です。
[コンテストリンク](https://atcoder.jp/contests/abc409)

# 問題一覧
- [【ABC409】A問題 - Conflict　考察から実装(c++)まで](https://qiita.com/hoppii007/items/7eb99788c8c8ff7c0bd1)
- [【ABC409】B問題 - Citation　考察から実装(c++)まで](https://qiita.com/hoppii007/items/6327ed54dae44b608503)
- [【ABC409】C問題 - Equilateral Triangle　考察から実装(c++)まで](https://qiita.com/hoppii007/items/343b7386696af3eef239)
- [【ABC409】D問題 - String Rotation　考察から実装(c++)まで](https://qiita.com/hoppii007/items/8c5093adea13a274d453)
- [【ABC409】E問題 - Pair Annihilation　考察から実装(c++)まで](https://qiita.com/hoppii007/items/92f4a5e02356bdb9fae7)
- 【ABC409】F問題 - Connecting Points　考察から実装(c++)まで <- イマココ

# F問題 - Connecting Points
[問題リンク](https://atcoder.jp/contests/abc409/tasks/abc409_f)

## 問題概要
二次元平面上に、$N$頂点$0$辺のグラフ$G$がある。$G$の二点間の距離をマンハッタン距離で定義する。
また、$G$の連結成分$A,B$の距離を、$A$の点と$B$の点の中で一番近い二点間の距離と定義する。
以下の三種類のクエリを$Q$回処理せよ。

- ```1 a b``` : $G$に頂点$(a,b)$を追加する。
- ```2``` 
    - $G$の異なる二つの連結成分で、距離が最小のもの全てをマージし、その最小の距離を表示する。
    - $G$の連結成分が1つしかないときは```-1```を表示する。
- ```3 u v``` : 頂点$u,v$が同じ連結成分にあれば```Yes```、違う連結成分に属していたら```No```を表示する。

### 制約
- $ 2 \le N \le 1500 $
- $ 1 \le Q \le 1500 $
- $ 0 \le x_i,y_i \le 10^9 $

## 考察
かなり素直に考えればいい。
とりあえず連結成分どうたらの問題で、切り離しがないので、UnionFindで管理すれば良さそう。

現状の全ての連結成分間の距離を常に持っておいて、```priority_queue```で小さい順に取り出す、とかでできそう。
クエリの数は$1500$以下で元々の頂点数も$1500$以下なので、出来得る連結成分の個数は最大でも$3000$個。
ということは、連結成分同士の組み合わせの数は最大でも$9 \times 10^6$。やっぱクエリ1で頂点が追加されるたびに、今までの連結成分ぜんぶとの距離を```priority_queue```に突っ込んでいけばよさそう！

計算量は$O((N+Q)^2 log (N+Q))$



## 実装
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
using vll = vector<ll>;
using vpll = vector<pll>;

struct UnionFind {
public:
    vll par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    vll kosu;
    ll Count; //全体として何個の集合があるか
    
    UnionFind(ll n) : par(n),kosu(n),Count(n) { //最初は全てが根であるとして初期化
        for(int i=0;i<n;i++){
            par[i] = i;
            kosu[i] = 1;
        }
    }

    ll root(ll x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(ll x, ll y) { // xとyの木を併合
        ll rx = root(x); //xの根をrx
        ll ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根
        kosu[ry] += kosu[rx];
        Count--;
    }

    bool same(ll x, ll y) { // 2つのデータx, yが属する木が同じならtrueを返す
        ll rx = root(x);
        ll ry = root(y);
        return rx == ry;
    }
    
    ll size(ll x){
        return kosu[root(x)];
    }
    ll size(){
        return Count;
    }
};

//(頂点iとjの距離がd)という情報を保持しておくための構造体
struct S{
    ll d,i,j;
    
    bool operator<(const S &other) const {
        return this->d > other.d;
    }
};

ll distance(pll a, pll b){
    return abs(a.first - b.first) + abs(a.second - b.second);
}

int main(void){
    //入力
    ll N,Q;
    cin>>N>>Q;
    
    vpll points(N);
    for(int i=0;i<N;i++) cin>>points[i].first>>points[i].second;
    
    //頂点数は最大でも3000個なので、3000用意しておけばいい
    UnionFind uf(3000);
    
    //頂点間の距離が小さい順に取り出すやつ
    priority_queue<S> q;
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            q.push(S{distance(points[i], points[j]), i,j});
        }
    }
    
    while(Q--){
        ll t;
        cin>>t;
        if(t == 1){
            //新しく追加された頂点と、今までの頂点との距離を優先度付きキューに入れていく
            ll a,b;
            cin>>a>>b;
            for(int i=0;i<points.size();i++){
                q.push(S{distance(points[i], {a,b}), i, (ll)points.size()});
            }
            points.push_back({a,b});
        }
        else if(t == 2){
            //違う頂点間の点がなければ、-1
            if(q.empty()){
                cout<<-1<<endl;
                continue;
            }
            ll mi = q.top().d;
            //距離が最小のやつらを全部くっつけていく
            while(!q.empty() && q.top().d == mi){
                uf.unite(q.top().i, q.top().j);
                q.pop();
            }
            //すでに同じ連結成分のやつは消していく
            while(!q.empty() && uf.same(q.top().i, q.top().j)) q.pop();
            
            cout<<mi<<endl;
        }
        else{
            //頂点u,vが同じ連結成分かどうかを、UnionFindを使って確認
            ll u,v;
            cin>>u>>v;
            cout<<(uf.same(u-1, v-1)?"Yes":"No")<<endl;
        }
    }
    return 0;
}


```