Algorithm
Problem Name: Mathematics -
https://www.hackerrank.com/challenges/most-distant/problem?isFullScreen=true
In this HackerRank in Mathematics -
Keko has N dots in a 2-D coordinate plane. He wants to measure the gap between the most distant two dots. To make the problem easier, Keko decided to change each dot's x or y coordinate to zero.
Help Keko calculate the distance!
Input Format
The first line contains an integer, N, the number of dots.
The next N lines each contain the integer coordinates of the dots in (x,y) fashion.
Constraints
2 <= n <= 106
-109 <= xi,yi <= 109
It is guaranteed that all dots are distinct, and either their x or y coordinate is equal to
.
Output Format
Print the distance between the most distant dots with an absolute error of, at most, 10-6.
Sample Input
4
-1 0
1 0
0 1
0 -1
Sample Output
2.000000
Explanation
In the sample, the most distant dots are located at (-1, 0) and (1, 0). The distance between them is 2.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <math.h>
double dist(long signed int a, long signed int b)
{
long unsigned int c = a*a + b*b;
double d = sqrt(c);
return d;
}
int main ()
{
int i, n;
scanf("%d", &n);
long signed int x[n], y[n];
for (i = 0; i < n; i++)
{
scanf("%ld %ld", &x[i], &y[i]);
}
double minx = x[0], maxx = x[0], miny = y[0], maxy = y[0], array[6], max = 0;
for (i = 1; i < n; i++)
{
if (x[i] < minx)
{
minx = x[i];
}
if (x[i] > maxx)
{
maxx = x[i];
}
if (y[i] < miny)
{
miny = y[i];
}
if (y[i] > maxy)
{
maxy = y[i];
}
}
array[0] = maxx - minx;
array[1] = maxy - miny;
array[2] = dist(minx, miny);
array[3] = dist(minx, maxy);
array[4] = dist(maxx, miny);
array[5] = dist(maxx, maxy);
for (i = 0; i < 6; i++)
{
if (array[i] > max)
{
max = array[i];
}
}
printf("%lf", max);
}
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
vector < double>d;
long int y_0=INT_MIN,x_0=INT_MIN,ny_0=INT_MAX,nx_0=INT_MAX;
while(t--){
long int x,y;
cin >> x >> y;
if(y == 0){
x_0 = max(x_0,x);
nx_0=min(nx_0,x);
}
else{
y_0 = max(y_0,y);
ny_0 = min(ny_0,y);
}
}
long int x_y = max(abs((x_0-nx_0)),abs(y_0-ny_0)),x,y;
d.push_back(sqrt(pow(x_y,2)));
x = max(abs(x_0),abs(nx_0));
y = max(abs(y_0),abs(ny_0));
d.push_back(sqrt(pow(x,2)+pow(y,2)));
if(d[0] >= d[1]) cout << setprecision(10) << d[0];
else cout << setprecision(10) << d[1];
return 0;
}
#3 Code Example with Java Programming
Code -
Java Programming
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
try (final Scanner scanner = new Scanner(System.in)) {
int minX = 0, minY = 0, maxX = 0, maxY = 0;
for (int n = scanner.nextInt(); n > 0; n--) {
final int x = scanner.nextInt();
final int y = scanner.nextInt();
minX = Math.min(minX, x);
minY = Math.min(minY, y);
maxX = Math.max(maxX, x);
maxY = Math.max(maxY, y);
}
final long x1 = Math.max(maxX, Math.abs(minX));
final long y1 = Math.max(maxY, Math.abs(minY));
final double r = Math.max(Math.max(maxX - minX, maxY - minY), Math.sqrt(x1 * x1 + y1 * y1));
System.out.print(BigDecimal.valueOf(r).setScale(6, RoundingMode.HALF_UP).toPlainString());
}
}
}
#4 Code Example with Python Programming
Code -
Python Programming
#!/bin/python3
import math
import os
import random
import re
import sys
#
# Complete the 'solve' function below.
#
# The function is expected to return a DOUBLE.
# The function accepts 2D_INTEGER_ARRAY coordinates as parameter.
#
def solve(coordinates):
xmin, xmax = lambda x: x[0], lambda x: -x[0]
ymin, ymax = lambda y: y[1], lambda y: -y[1]
xmin = sorted(coordinates, key=xmin)[0][0]
xmax = sorted(coordinates, key=xmax)[0][0]
ymin= sorted(coordinates, key=ymin)[0][1]
ymax = sorted(coordinates, key=ymax)[0][1]
'''Compute 6 distances'''
dx, dy = xmax - xmin, ymax - ymin # diagonals
'''1st side'''
d1 = math.sqrt(xmin**2 + ymax**2)
'''2nd side'''
d2 = math.sqrt(xmax**2 + ymax**2)
'''3rd side'''
d3 = math.sqrt(xmin**2 + ymin**2)
'''4th side'''
d4 = math.sqrt(xmax**2 + ymin**2)
d = max([dx, dy, d1, d2, d3 , d4])
return F'{d:.6f}'
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(input().strip())
coordinates = []
for _ in range(n):
coordinates.append(list(map(int, input().rstrip().split())))
result = solve(coordinates)
fptr.write(str(result) + '\n')
fptr.close()