yukicoder : No.168 ものさし

問題文に引っ張られて整数型でいいところをdouble型にしてしまい、精度不足で1WA。
http://yukicoder.me/problems/296

問題

２次元座標上にN個の点P_1～P_Nがある。
長さが10の整数倍のものさしがある。

ものさしの長さをLとすると、距離L以下の点同士を線で結ぶことができる。
P_1とP_Nを(間に他の点を経由してもいいので)結ぶことができる最短の長さのものさしを求めよ。

解法

ものさしの長さLを二分探索する。
ダイクストラなど手の込んだアルゴリズムを使わなくても、Union-Findで距離L以下の点を連結していけば、1回あたりO(N^2*α(N))の時間で判定できる。

以下のコードでは、精度によるミスを防ぐため小数を使わないよう二乗距離で判定している。

別解としては、P1とPNがつながるところまで最小全域木を求めていく、などの方法もある。

class UF {
	public:
	int um;
	vector<int> ufpar,ufrank,ufcnt;
	UF(int um_=100002) { um=um_; ufrank=vector<int>(um,0); ufcnt=vector<int>(um,1); for(int i=0;i<um;i++) ufpar.push_back(i);}
	int operator[](int x) {return (ufpar[x]==x)?(x):(ufpar[x] = operator[](ufpar[x]));}
	int count(int x) { return ufcnt[operator[](x)];}
	void unite(int x,int y) {
		x = operator[](x); y = operator[](y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x];
		else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

int N;
ll X[1010],Y[1010];
ll D[1010][1010];

bool ok(ll v) {
	UF uf(1010);
	int x,y;
	FOR(x,N) FOR(y,N) if(D[x][y]<=v*v) uf.unite(x,y);
	return uf[0]==uf[N-1];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	FOR(x,N) FOR(y,N) D[x][y]=(X[x]-X[y])*(X[x]-X[y])+(Y[x]-Y[y])*(Y[x]-Y[y]);
	
	ll hoge=(1LL<<31)-1;
	for(i=30;i>=0;i--) if(ok(hoge-(1LL<<i))) hoge -= 1LL<<i;
	cout<<(hoge+9)/10*10<<endl;
}

まとめ

結構みんな普通にdouble使って通ってるなぁ。