# 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 can even save a lot of memory when dealing with a stream of data. If we read the list from the standard input, we can avoid to keep in memory all the input array. So we can deal with millions of lines and still using few bytes of RAM.

In the following example, we iterate on Rust lines: io::Lines<T> which is an iterator to deal with lines of text coming from streams, like standard input or a tcp socket.

  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 34 35 36 37 38 39 40 41 42 43 44  fn euclidean(x: i64, y: i64) -> f64 { (((x * x) + (y * y)) as f64).sqrt() } fn parse_point(s: String) -> Option<(i64, i64)> { let (x, y) = s.split_once(' ')?; let x: i64 = x.parse().ok()?; let y: i64 = y.parse().ok()?; Some((x, y)) } fn solve(lines: io::Lines) -> f64 { let mut min_ver = 10_000_000_000; let mut max_ver = -10_000_000_000; let mut min_hor = 10_000_000_000; let mut max_hor = -10_000_000_000; lines .filter_map(|r| r.ok()) .filter_map(parse_point) .for_each(|(x, y)| { if x == 0 { min_ver = min(min_ver, y); max_ver = max(max_ver, y); } else if y == 0 { min_hor = min(min_hor, x); max_hor = max(max_hor, x); } }); let distances = [ (max_hor - min_hor) as f64, (max_ver - min_ver) as f64, euclidean(min_hor, max_ver), euclidean(min_hor, min_ver), euclidean(max_hor, max_ver), euclidean(min_hor, min_ver), ]; *distances .iter() .max_by(|a, b| a.partial_cmp(b).unwrap()) .unwrap() } 
We've worked on this challenge in these gyms: modena  padua