# Most Distant

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 using namespace std; double euclidean(double x, double y) { return sqrt(x*x + y*y); } int main() { int n; cin >> n; vector x(n), y(n); for (auto i=0; i> x[i] >> y[i]; } auto mmx = minmax_element(begin(x), end(x)); auto mmy = minmax_element(begin(y), end(y)); array 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 distances = { fabs(*leftmost - *rightmost), fabs(*lowest - *highest), euclidean(*leftmost, *highest), euclidean(*leftmost, *lowest), euclidean(*rightmost, *highest), euclidean(*rightmost, *lowest) }; 
We've worked on this challenge in these gyms: modena