Most Distant · Coding Gym

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)
};