#226254 (C++11（廃止可能性あり）) No.168 ものさし

• 問題: No.168 ものさし
• ユーザー: ushitora_anqou
• 提出日時: 2017-12-26 23:11:58
• 言語: C++11（廃止可能性あり） (gcc 13.3.0)
• 結果: AC
• 実行時間: 71 ms / 2,000 ms
• コード長: 1,847 bytes
• コンパイル時間: 1,279 ms
• コンパイル使用メモリ: 160,124 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-12-24 07:21:52
• 合計ジャッジ時間: 2,391 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

ファイルパターン	結果
sample	AC * 4
other	AC * 19

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ld = long double;
const int INF = 1 << 29;
const ll LINF = 1l << 61;
const ld PI = abs(acos(-1));
#define pq priotity_queue
#define mp make_pair
#define P pair
#define rep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrep(i, a, b) for (ll i = (a); i >= (b); i--)
#define cbuf(buf, init) memset(buf, init, sizeof(buf))
#define modp(x, y) (((y) + (x) % (y)) % (y))
#define divd(x, y) (static_cast<double>(x) / static_cast<double>(y))
#define sq(x) (x) * (x)
template <ll SIZE>
class UnionFind {
public:
    using type = ll;  // must be integer type
private:
    std::array<ll, SIZE> parent_, rank_;
public:
    UnionFind()
    {
        for (ll i = 0; i < SIZE; i++) {
            parent_[i] = i;
            rank_[i] = 0;
        }
    }
    ll operator[](ll x)
    {
        if (parent_[x] == x)
            return x;
        else
            return parent_[x] = (*this)[parent_[x]];
    }
    void unite(ll x, ll y)
    {
        x = (*this)[x];
        y = (*this)[y];
        if (x == y) return;
        if (rank_[x] < rank_[y]) {
            parent_[x] = y;
        }
        else {
            parent_[y] = x;
            if (rank_[x] == rank_[y]) rank_[x]++;
        }
    }
};
ll N, X[2000], Y[2000];
bool C(ll l)
{
    UnionFind<2000> uf;
    rep(i, 0, N)
    {
        rep(j, 0, N)
        {
            if (sq(X[j] - X[i]) + sq(Y[j] - Y[i]) <= sq(l)) uf.unite(i, j);
        }
    }
    return (uf[0] == uf[N - 1]);
}
int main()
{
    //
    cin >> N;
    rep(i, 0, N) { cin >> X[i] >> Y[i]; }
    ll lb = 0, ub = 2E9;
    while (ub - lb > 1) {
        ll mid = (lb + ub) / 2;
        mid = mid / 10 * 10;
        if (mid == lb) break;
        if (C(mid))
            ub = mid;
        else
            lb = mid;
    }
    cout << ub << endl;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX