See the original problem on HackerRank.
Solutions
Since every point has either \( x \) or \( y \) to 0, only 4 points can contribute to the final solution:
- the rightmost point - max \( x \)
- the leftmost point - min \( x \)
- the highest point - max \( y \)
- the lowest point - min \( y \)
Basically, we can ignore all the internal points.
Then, it’s just the matter of calculating the max distance among such points (the total number of pair-wise combinations is 6).
The distance between two points \( (x_1, y_1), (x_2, y_2) \) is just the Euclidean distance:
\( \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} \)
Just bear in mind that either \( x_2 \) or \( y_2 \) is zero.
Actually, we need to apply this relation only when considering one point on the x-axist and one on the y-axis. In the other (two) cases, their distance is just the absolute value of their difference.
Here is a solution in C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include <bits/stdc++.h>
using namespace std;
double euclidean(double x, double y)
{
return sqrt(x*x + y*y);
}
int main()
{
int n; cin >> n;
vector<double> x(n), y(n);
for (auto i=0; i<n; ++i)
{
cin >> x[i] >> y[i];
}
auto mmx = minmax_element(begin(x), end(x));
auto mmy = minmax_element(begin(y), end(y));
array<double, 6> distances = {
fabs(*mmx.first - *mmx.second),
fabs(*mmy.first - *mmy.second),
euclidean(*mmx.second, *mmy.second),
euclidean(*mmx.second, *mmy.first),
euclidean(*mmx.first, *mmy.second),
euclidean(*mmx.first, *mmy.first)
};
auto maxVal = max_element(begin(distances), end(distances));
cout << setprecision(12) << fixed << *maxVal;
}
|
In C++17, we can make the core part of the snippet above a bit nicer:
1
2
3
4
5
6
7
8
9
10
11
|
auto [leftmost, rightmost] = minmax_element(begin(x), end(x));
auto [lowest, highest] = minmax_element(begin(y), end(y));
array<double, 6> distances = {
fabs(*leftmost - *rightmost),
fabs(*lowest - *highest),
euclidean(*leftmost, *highest),
euclidean(*leftmost, *lowest),
euclidean(*rightmost, *highest),
euclidean(*rightmost, *lowest)
};
|