結果

問題 No.168 ものさし
ユーザー latte0119latte0119
提出日時 2015-03-20 01:09:49
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 73 ms / 2,000 ms
コード長 2,246 bytes
コンパイル時間 1,023 ms
コンパイル使用メモリ 96,368 KB
実行使用メモリ 15,712 KB
最終ジャッジ日時 2024-06-06 14:51:33
合計ジャッジ時間 2,339 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 18 ms
6,488 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 4 ms
5,376 KB
testcase_11 AC 17 ms
6,492 KB
testcase_12 AC 53 ms
15,704 KB
testcase_13 AC 73 ms
15,708 KB
testcase_14 AC 73 ms
15,712 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 3 ms
5,376 KB
testcase_18 AC 6 ms
5,376 KB
testcase_19 AC 68 ms
15,692 KB
testcase_20 AC 72 ms
15,580 KB
testcase_21 AC 72 ms
15,580 KB
testcase_22 AC 73 ms
15,580 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<vector>
#include<map>
#include<climits>
#include<set>
#include<queue>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<string>
#include<bitset>
#include<cstring>
#include<list>
#include<iterator>
using namespace std;
typedef vector<string>vs;
typedef vector<int>vi;
typedef vector<vi>vvi;
typedef pair<int,int>pii;
typedef long long ll;
typedef pair<ll,ll>pll;
#define rrep(i,x,n) for(int i=(x);i<(n);++i)
#define rep(i,x) rrep(i,0,(x))
#define fi first
#define se second
#define each(i,c) for(typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define pb push_back

class union_find{
private:
    int n;
    vector<int>p,r;
public:
    void init(int n_){
        n=n_;
        p=vector<int>(n);
        r=vector<int>(n,0);
        for(int i=0;i<n;i++)p[i]=i;
    }
    union_find(int n_=0){
        init(n_);
    }
    int get_par(int x){
        return p[x]==x?x:p[x]=get_par(p[x]);
    }
    void unite(int x,int y){
        x=get_par(x);
        y=get_par(y);
        if(x==y)return;
        if(r[x]<r[y])p[x]=y;
        else p[y]=x;
        r[y]+=r[x]==r[y]?1:0;
    }
    bool same(int x,int y){
        return get_par(x)==get_par(y);
    }
};

struct data{
    ll x,y,len;
    data(ll a,ll b,ll c):
        x(a),y(b),len(c){}
    data(){}

    bool operator<(const data &d)const{
        if(len!=d.len)return len<d.len;
        if(x!=d.x)return x<d.x;
        return y<d.y;
    }
};

int main(){
    int N;
    cin>>N;
    ll x[1000],y[1000];
    rep(i,N)cin>>x[i]>>y[i];

    vector<data>V;
    rep(i,N)rrep(j,i+1,N)V.pb(data(i,j,(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));

    sort(all(V));

    union_find uf(N);

    ll ma=0;
    rep(i,V.size()){
        data d=V[i];
        ma=max(ma,d.len);
        uf.unite(d.x,d.y);

        if(uf.same(0,N-1))break;
    }
    ll ub=2000000000,lb=0;
    while(ub-lb>1){
        ll mid=(ub+lb)/2;
        if(mid*mid>=ma)ub=mid;
        else lb=mid;
    }
    if(ub%10)ub=ub/10*10+10;
    else ub=ub/10*10;

    cout<<ub<<endl;

    return 0;
}
0