Atcoder ARC #010 D. 情報伝播

D: 情報伝播 - AtCoder Regular Contest 010 | AtCoder

n人の青木くんとm人のスパイが平面上にいて、青木くんは、自分を中心とする任意の半径をもつ円の内部に情報を拡散できる。スパイに情報がもれないように、青木くん全員に情報を行き渡らせるために直接情報を伝えなければならない青木くんの最小人数を求める問題。各青木くんについて、最も近い距離にいるスパイまでの距離を持たせて、その範囲にいる他の青木くんに向かって有向グラフを張ると考えるのが自然である。そのあとは、強連結成分分解をして、トポロジカルソート順の小さいものからdfsをして、その途切れる回数を求めれば良い。

#include "bits/stdc++.h"
using namespace std;

double dis(int x, int y, int s, int t) {
        return sqrt((double)(x - s) * (double)(x - s) + (double)(y - t) * (double)(y - t));
};

int V;
vector<int> g[101010];
vector<int> rg[101010];
vector<int> order;
bool used[101010];
int cmp[101010];

void add_edge(int from, int to) {
        g[from].push_back(to);
        rg[to].push_back(from);
}
void dfs(int v) {
        used[v] = true;
        for (auto i : g[v]) if (!used[i]) dfs(i);
        order.push_back(v);
}
void rdfs(int v, int k) {
        used[v] = true;
        cmp[v] = k;
        for (auto i : rg[v]) if (!used[i]) rdfs(i, k);
}
int StronglyConnectedComponent() {
        memset(used, 0, sizeof(used));
        order.clear();
        for (int i = 0; i < V; i ++) if (!used[i]) dfs(i);
        memset(used, 0, sizeof(used));
        int k = 0;
        for (int i = order.size() - 1; i >= 0; i --) if (!used[order[i]]) rdfs(order[i], k ++);
        return k;
}

int main() {
        int i, j;
        int n, x, y;
        cin >> n;
        V = n;
        vector<pair<int, int>> f;//person
        for (i = 0; i < n; i ++) {
                cin >> x >> y;
                f.emplace_back(x, y);
        }
        int m;
        cin >> m;
        if (m == 0) { 
                cout << 1 << endl;
                return 0;
        }
        vector<pair<int, int>> s;//spy
        for (i = 0; i < m; i ++) {
                cin >> x >> y;
                s.emplace_back(x, y);
        }
        vector<pair<pair<int, int>, int>> fs;//combined
        for (i = 0; i < n; i ++) fs.emplace_back(f[i], 1);
        for (i = 0; i < m; i ++) fs.emplace_back(s[i], 0);
        sort(fs.begin(), fs.end());//すべてをx座標の小さい順に並べる
        int fp = 0;
        vector<double> dist(n);//各青木くんの、一番近いスパイまでの距離
        for (i = 0; i < fs.size(); i ++) {
                if (fs[i].second == 0) continue;
                double d = 100000000000.0;
                int front = i;
                int back = i;
                while (d > (fs[front].first.first - fs[i].first.first)) {
                        front ++;
                        if (front > fs.size() - 1) break;
                        if (fs[front].second == 1) continue;
                        d = min(d, dis(fs[front].first.first, fs[front].first.second, fs[i].first.first, fs[i].first.second));
                }
                while (d > (fs[i].first.first - fs[back].first.first)) {
                        back --;
                        if (back < 0) break;
                        if (fs[back].second == 1) continue;
                        d = min(d, dis(fs[back].first.first, fs[back].first.second, fs[i].first.first, fs[i].first.second));
                }
                dist[fp ++] = d;
        }
        //これ以降、スパイは考えなくて良い
        sort(f.begin(), f.end());
        for (i = 0; i < n; i ++) {
                int front = i;
                int back = i;
                while (dist[i] > (double)(f[front].first - f[i].first)) {
                        front ++;
                        if (front > f.size() - 1) break;
                        double d = dis(f[front].first, f[front].second, f[i].first, f[i].second);
                        if (d < dist[i]) {
                                add_edge(i, front);
                        }
                }                           
                while (dist[i] > (double)(f[i].first - f[back].first)) {
                        back --;
                        if (back < 0) break;
                        double d = dis(f[back].first, f[back].second, f[i].first, f[i].second);
                        if (d < dist[i]) {
                                add_edge(i, back);
                        }
                }
        }
        StronglyConnectedComponent();
        vector<pair<int, int>> jun;
        for (i = 0; i < n; i ++) jun.emplace_back(cmp[i], i);
        sort(jun.begin(), jun.end());
        for (i = 0; i < n; i ++) used[i] = false;
        int ans = 0;
        for (i = 0; i < n; i++) {
                if (!used[jun[i].second]) { 
                        dfs(jun[i].second);
                        ans ++;
                }
        }
        cout << ans << endl;
        return 0;
}

実装するだけ