結果

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