結果

問題 No.168 ものさし
ユーザー y_taira_cy_taira_c
提出日時 2017-07-08 22:58:38
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 42 ms / 2,000 ms
コード長 2,445 bytes
コンパイル時間 934 ms
コンパイル使用メモリ 84,448 KB
実行使用メモリ 10,976 KB
最終ジャッジ日時 2023-08-25 21:05:51
合計ジャッジ時間 2,251 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
4,968 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 10 ms
4,712 KB
testcase_12 AC 29 ms
8,604 KB
testcase_13 AC 42 ms
10,928 KB
testcase_14 AC 42 ms
10,968 KB
testcase_15 AC 1 ms
4,380 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 4 ms
4,376 KB
testcase_19 AC 30 ms
10,780 KB
testcase_20 AC 31 ms
10,976 KB
testcase_21 AC 32 ms
10,924 KB
testcase_22 AC 32 ms
10,916 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
0