Official

B - Longest Segment Editorial by penguinman


この問題においては \(N\) の制約が \(100\) 以下と小さいため、すべての \((i,j)\ (1 \leq i \lt j \leq N)\) について(このような組は \(\frac{N(N-1)}{2}\) 個ある)\(i\) 個目の点と \(j\) 個目の点を結ぶ線分の長さを求めた上でその最大値を取っても実行時間制限に余裕を持って間に合います。

\(2\) 点を結ぶ線分の長さはそれらのユークリッド距離に等しく、その値は \(\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}\) となります。

これらを踏まえてコードを書くと、以下のようになります。計算量は \(O(N^2)\) です。

実装例 (Python)

from math import sqrt
N = int(input())
x = [0]*N
y = [0]*N
for i in range(N):
    x[i],y[i] = map(int,input().split())
ans = 0
for i in range(N):
    for j in range(i+1,N):
        X = x[i]-x[j]
        Y = y[i]-y[j]
        ans = max(ans,sqrt(X*X+Y*Y))
print(ans)

なお、C++ 等一部の言語においてはデフォルトでの小数出力の桁数がこの問題において許容される誤差の範囲を超えている(例えば小数点以下 \(5\) 桁までしか表示されないなど)ため、以下のようなコードは不正解となります。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
	int N; cin >> N;
	vector<int> x(N),y(N);
	for(int i=0; i<N; i++) cin >> x[i] >> y[i];
	double ans = 0;
	for(int i=0; i<N; i++){
		for(int j=i+1; j<N; j++){
			int X = x[i]-x[j], Y = y[i]-y[j];
			ans = max(ans,sqrt(X*X+Y*Y));
		}
	}
	cout << ans << endl;
}

このような場合には、std::fixed と std::setprecision を用いるなどして小数出力の桁数を指定すればよいです。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
	int N; cin >> N;
	vector<int> x(N),y(N);
	for(int i=0; i<N; i++) cin >> x[i] >> y[i];
	double ans = 0;
	for(int i=0; i<N; i++){
		for(int j=i+1; j<N; j++){
			int X = x[i]-x[j], Y = y[i]-y[j];
			ans = max(ans,sqrt(X*X+Y*Y));
		}
	}
	cout << fixed << setprecision(10) << ans << endl;
}

posted:
last update: