結果

問題 No.168 ものさし
コンテスト
ユーザー hogeover30
提出日時 2015-03-24 02:46:09
言語 C++11(old_compat)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -include bits/stdc++.h -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 77 ms / 2,000 ms
コード長 1,116 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,532 ms
コンパイル使用メモリ 173,652 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-03-08 16:01:55
合計ジャッジ時間 2,682 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

struct unionfind {
    vector<int> id;
    int size;
    unionfind(int size_):size(size_) {
        id=vector<int>(size);
        for(int i=0;i<size;++i) id[i]=i;
    }
    int root(int x) { return id[x]=id[x]==x?x:root(id[x]); }
    void unite(int x, int y) { x=root(x); y=root(y); if (x!=y) id[x]=y; }
    bool same(int x, int y) { return root(x)==root(y); }
};

vector<pair<ll, ll>> p;
int n;

ll dist(int i, int j)
{
#define sqr(x) ((x)*(x))
    return sqr(p[i].first-p[j].first)+sqr(p[i].second-p[j].second);
}
int main()
{
    while (cin>>n) {
        p=vector<pair<ll,ll>>(n);
        for(auto& v: p) { ll x, y; cin>>x>>y; v=make_pair(x, y); }
        ll L=0, R=sqrt(dist(0, n-1))*2;
        while (R-L>2) {
            ll M=(L+R)/2;
            unionfind a(n);
            for(int i=0;i<n;++i) for(int j=0;j<n;++j) if (i!=j and dist(i, j)<=M*M)
                a.unite(i, j);
            if (a.same(0, n-1))
                R=M+1;
            else
                L=M;
        }
        cout<<(R-1+9)/10*10<<endl;
    }
}
0