Official

B - Longest Segment Editorial by en_translator


Since the constraint of \(N\) is at most \(100\), which is small enough, so we can compute for every pair \((i,j)\ (1 \leq i \lt j \leq N)\) the length of the segment connecting the \(i\)-th and the \(j\)-th segment and find the maximum value without exceeding the time limit in good time.

The length of a segment connecting two points is equal to their Euclidean distance, whose value is \(\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}\).

Based on this fact, the code can be written as follows. The total complexity is \(O(N^2)\).

Sample code (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)

Note that, when outputting decimals in some languages like C++, the number of digits of the fractional part is not enough for the extent of error tolerance (for example, only \(5\) digits of fractional part is output), so the following sample code will not be accepted.

Sample code (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;
}

In such case, specify the number of digits to be output using std::fixed and std::setprecision.

Sample code (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: