結果

問題 No.168 ものさし
ユーザー y_taira_c
提出日時 2017-07-08 22:58:38
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 46 ms / 2,000 ms
コード長 2,445 bytes
コンパイル時間 1,304 ms
コンパイル使用メモリ 84,752 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2024-12-24 07:19:11
合計ジャッジ時間 2,304 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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

#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;
typedef long long int ll;
#define REP(i,n) for(int i=0; i<n; ++i )
#define REPR(i,n) for(int i=n; i>=0; --i)
#define FOR(i,a,n) for(int i=a; i<n; ++i )
#define FORR(i,a,n) for(int i=n; i>=a; --i)
#define VDOUT(x) cerr << #x << "\n";for(auto i : x ) cerr << "  " << i << "\n";
#define DOUT(x) cerr << #x << " = " << x << "\n";
#define COUT(x) cout << x << "\n";
#define COUT2(x,y) cout <<x << " " << y << "\n";
#define COUT3(x,y,z) cout << x << " " << y << " " << z << "\n"; 
#define INI ios::sync_with_stdio(false);cin.tie(0)
#define ALL(x) x.begin(),x.end()
typedef long long int h_int;
class UnionFind
{
private:
    std::vector<h_int> uni_;
    h_int Root(h_int a)
    {
        if (uni_[a] < 0) return a;
        return uni_[a] = Root(uni_[a]);
    }
public:
    UnionFind(h_int max_n)
    {
        uni_.resize(max_n, -1);
    }
    bool Connect(h_int a, h_int b)
    {
        a = Root(a);
        b = Root(b);
        if (a == b) return false;
        if (uni_[a] > uni_[b]) std::swap(a, b);
        uni_[a] += uni_[b];
        uni_[b] = a;
        return true;
    }
    bool Same(h_int a, h_int b)
    {
        return Root(a) == Root(b);
    }
    h_int CountRoot()
    {
        h_int cnt = 0;
        for (auto i : uni_)
        {
            if (i < 0) ++cnt;
        }
        return cnt;
    }
};
struct Vector
{
    h_int x_;
    h_int y_;
    Vector() :x_(0), y_(0) {}
    Vector(h_int x, h_int y) :x_(x), y_(y)
    {}
    h_int GetDistance(const Vector& v)
    {
        return (x_ - v.x_)*(x_ - v.x_) + (y_ - v.y_)*(y_ - v.y_);
    }
};
vector<vector<h_int>> dis;
bool Solve(h_int x)
{
    x *= 10;
    UnionFind uni(dis.size());
    REP(i, dis.size())
    {
        FOR(j, i + 1, dis.size())
        {
            if (dis[i][j] <= x*x)
            {
                uni.Connect(i, j);
            }
        }
    }
//  DOUT(x);
//  DOUT(uni.CountRoot());
    return uni.Same(0, dis.size() - 1);
}
signed main()
{
    INI;
    vector<Vector> v;
    h_int n;
    cin >> n;
    v.resize(n);
    REP(i, n)
    {
        h_int x, y;
        cin >> x >> y;
        v[i] = Vector(x, y);
    }
    REP(i, n)
    {
        vector<h_int> tmp;
        REP(j, n)
        {
            if (i > j)
            {
                tmp.push_back(dis[j][i]);
            }
            else if (i == j)
            {
                tmp.push_back(0);
            }
            else
            {
                tmp.push_back(v[i].GetDistance(v[j]));
            }
        }
        dis.push_back(tmp);
    }
    
    h_int left=0;
    h_int right = 1000000000;
    while (abs(left - right) > 1)
    {
        h_int mid = (left + right) / 2;
        if (Solve(mid))
        {
            right = mid;
        }
        else
        {
            left = mid;
        }
    }
    COUT(right*10);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0