結果

問題 No.168 ものさし
ユーザー moko_freedom
提出日時 2018-03-16 13:30:47
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 172 ms / 2,000 ms
コード長 2,490 bytes
コンパイル時間 1,643 ms
コンパイル使用メモリ 167,684 KB
実行使用メモリ 11,508 KB
最終ジャッジ日時 2024-12-21 14:24:47
合計ジャッジ時間 3,573 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
using namespace std;
#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846
typedef long long ll;
typedef pair<int,ll> P;
typedef pair<ll,P> PP;
//-----------------------------------------------------------------------------
template< typename T >
struct Kruskal {
    // Kruskalに必要なライブラリ開始。
    struct Edge {
        int from,to;
        T cost;
        Edge(int to,T cost):from(-1),to(to),cost(cost) {}
        Edge(int from,int to,T cost):from(from),to(to),cost(cost) {}
        bool operator<(const Edge &e) const {
            return cost<e.cost;
        }
    };
    using Edges=vector< Edge >;
    struct UnionFind {
        vector<int> data;
        UnionFind(int size):data(size,-1) {}
        bool unite(int x,int y) {
            x=root(x),y=root(y);
            if(x!=y) {
                if(data[y]<data[x]) swap(x,y);
                data[x]+=data[y],data[y]=x;
            }
            return x!=y;
        }
        bool same(int x,int y) {
            return root(x)==root(y);
        }
        int root(int x) {
            return data[x]<0?x:data[x]=root(data[x]);
        }
        int size(int x) {
            return -data[root(x)];
        }
    };
    // Kruskalに必要なライブラリ終了。
    int n;
    Edges edges;
    Kruskal() {}
    Kruskal(int _n):n(_n) {}
    void add_edge(int u,int v,T c) {
        edges.emplace_back(u,v,c);
    }
    void input(int m) {
        int a,b;T c;
        for(int i=0;i<m;i++) {
            cin>>a>>b>>c;
            add_edge(a,b,c);
        }
    }
    bool kruskal(ll mid) {
        //cout<<"mid "<<mid<<endl;
        UnionFind uf(n);
        //cout<<"after uf"<<endl;
        for(auto &e:edges) {
            if(!uf.same(e.from,e.to)&&e.cost<=mid*mid) {
                //cout<<"from="<<e.from<<",to="<<e.to<<endl;
                uf.unite(e.from,e.to);
            }
        }
        //for(int i=0;i<n;i++) cout<<uf.root(i)<<' ';
        //cout<<endl;
        return uf.same(0,n-1);
    }
    void show() {
        for(auto e:edges) cout<<'('<<e.from<<','<<e.to<<','<<e.cost<<')'<<endl;
    }
    void SORT() {
        sort(edges.begin(),edges.end());
    }
};
int n,x[1000],y[1000];
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>n;
    REP(i,n) cin>>x[i]>>y[i];
    Kruskal<ll> G(n);
    REP(i,n) {
        FOR(j,i+1,n) {
            ll X=abs(x[i]-x[j]),Y=abs(y[i]-y[j]);
            G.add_edge(i,j,X*X+Y*Y);
        }
    }
    //G.show();
    G.SORT();
    ll ub=(ll)1e9,lb=0;
    while(ub-lb>1) {
        ll mid=(ub+lb)/2;
        if(G.kruskal(mid*10)) ub=mid;
        else lb=mid;
        //cout<<"ub,lb="<<ub<<' '<<lb<<endl;
    }
    cout<<ub*10<<endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0