村の道路計画 [パソコン甲子園2016 予選 H]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0342?year=2016

前提知識

• 凸包
• 最小全域木（実際には少し違うけど）のクラスカル法
• UnionFind（最小全域木の構築で使用）

考察過程

1. 「幾何っぽさ」「村を構成するどの2つの集落を結んだまっすぐな線も村の外を通らない」というところから凸包
2. 凸包が村を囲む境界線となる
3. あとは、境界線上にない道を廃止するという部分である
4. 全体を連結にして、道の長さの合計を最小化するといえば最小全域木である
5. 木にはならないが、クラスカル法を使えば連結かつ道の長さの合計を最小化できる

解法

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0342/judge/3140168/C++14

アルゴリズムの知識を問われるような問題。
問題を2段階で解いていく。
　
convexAndMerge関数
まず村を囲む境界線を用意して、その道の長さを答えに加えよう。
村を囲む境界線は凸包になっている。
凸包を計算して、それを道として採用しよう。
ついでに、凸包で使われた頂点は全て連結になるのでUnionFindで連結しておく。
　
kruskal関数
与えられた村の辺を使ってクラスカル法を行う。

int V, R; P po[101];
int S[1010], T[1010];
UnionFind uf;
double ans;
//---------------------------------------------------------------------------------------------------
void convexAndMerge() {
    G graph;
    rep(i, 0, V) graph.push_back(po[i]);
    auto ch = convex_hull(graph);

    int n = ch.size();
    vector<int> chv;
    rep(i, 0, n) {
        rep(v, 0, V) if (abs(ch[i] - po[v]) < EPS) {
            chv.push_back(v);
            break;
        }
    }

    rep(i, 0, n) {
        int a = chv[i];
        int b = chv[(i + 1) % n];
        ans += abs(po[a] - po[b]);
        uf(a, b);
    }
}
//---------------------------------------------------------------------------------------------------
void kruskal() {
    vector<pair<double, int>> edges;
    rep(i, 0, R) {
        int a = S[i], b = T[i];
        edges.push_back({ abs(po[a] - po[b]), i });
    }
    sort(all(edges));

    fore(p, edges) {
        double cst = p.first;
        int a = S[p.second];
        int b = T[p.second];

        if (uf[a] != uf[b]) {
            ans += cst;
            uf(a, b);
        }
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> V >> R;
    rep(i, 0, V) {
        int x, y; cin >> x >> y;
        po[i] = P(x, y);
    }
    rep(i, 0, R) {
        cin >> S[i] >> T[i];
        S[i]--; T[i]--;
    }

    uf.init(V);

    convexAndMerge();
    kruskal();
    
    printf("%.10f\n", ans);
}