結果

問題 No.168 ものさし
ユーザー moti
提出日時 2015-04-09 13:12:29
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 206 ms / 2,000 ms
コード長 1,081 bytes
コンパイル時間 1,238 ms
コンパイル使用メモリ 162,800 KB
実行使用メモリ 11,096 KB
最終ジャッジ日時 2024-12-24 07:08:03
合計ジャッジ時間 3,566 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
struct UnionFind
{
    vector<int> rank;
    vector<int> rid;
    UnionFind(int n) {
        rank.resize(n);
        rid.assign(n, -1);
    }
    void unite(int u, int v) {
        u = root(u), v = root(v);
        if(u == v) { return ; }
        if(rank[u] < rank[v]) {
            rid[u] = v;
        }
        else {
            rid[v] = u;
            if(rank[u] == rank[v]) {
                rank[u]++;
            }
        }
    }
    bool same(int u, int v) {
        return root(u) == root(v);
    }
    int root(int x) {
        if(rid[x] < 0) return x;
        else return rid[x] = root(rid[x]);
    }
};
typedef long long ll;
ll N;
ll px[1010], py[1010];
#define SQ(x) ((x)*(x))
bool OK(ll x) {
    UnionFind uni(N*N);
    rep(i, N) {
        REP(j, i+1, N) {
            if(SQ(px[i]-px[j])+SQ(py[i]-py[j]) <= x*x) {
                uni.unite(i, j);
            }
        }
    }
    return uni.same(0, N-1);
}
int main() {
    cin >> N;
    rep(i, N) {
        cin >> px[i] >> py[i];
    }
    ll L = 0, R = 2*1e9;
    while(R-L>1) {
        ll M = (L+R)/2;
        if(OK(M)) {
            R = M;
        }
        else {
            L = M;
        }
    }
    cout << (R+9)/10*10 << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0