Algorithm


Problem Name: Mathematics - Most Distant

Problem Link: https://www.hackerrank.com/challenges/most-distant/problem?isFullScreen=true

In this HackerRank in Mathematics - Most Distant solutions,

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);
}
Copy The Code & Try With Live Editor

#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;
}
Copy The Code & Try With Live Editor

#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());
    }
  }
}
Copy The Code & Try With Live Editor

#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()
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Russian Peasant Exponentiation solution in Hackerrank - Hacerrank solution C, C++, C#, java, js, Python
Next
[Solved] Possible Path solution in Hackerrank - Hacerrank solution C, C++, Python