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)
};
|
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<T: BufRead>(lines: io::Lines<T>) -> 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()
}
|