Maximum Time

In this approach, we will sort all the points by their X Coordinates. Then we will iterate through every possible coordinate combination and find the maximum distance among all points.

Then divide the maximum distance by speed to find the maximum time.
 

Algorithm:

• Set maxDistance as 0
• Sort the locations array
• Iterate i from 0 to n - 1
  • Iterate j from i + 1 to n -1
    • Set distance as sum of the absolute value of (locations[i][0] + locations[j][0])^2 and absolute value of (locations[i][0] + locations[j][0]) ^ 2
    • Set maxDistance as the maximum of distance and maxDistance
• Set the float ans as maxDistance  divided by X
• Round ans to 6 floating points
• Finally, return ans

This approach will use the convex hull of the given points, as the two points with the maximum distance will be present on the convex hull. After getting the maximum distance, we can find the maximum time by dividing it by speed.

For this algorithm, we also need to know:

• To get the direction of point A to point B, with respect to point O, we can from vectors OA and OB and take their cross products.
• If the scalar product of two vectors OAxOB is negative, going from point A to B is clockwise. And if the scalar product is 0, then they are colinear.
• The absolute value of the scalar product of two vectors is equal to the area of the parallelogram formed by them, and it’s twice the area of the triangle formed by them.

Then we will apply the rotating calliper algorithm to find the two points.

Rotating Caliper Algorithm:

Step 1: Get the Convex Hull in a clockwise or counterclockwise manner.

Step 2: Finding Lower and Upper Section of Hull

There are N points of the convex hull which are P1, P2, …. PN, in a counterclockwise direction.

• Any point Pk antipodal to a point Pi will make a triangle of the largest area with two other points being Pi and P(i-1).
• We can find the antipodal point to point P1.
• Take Points P1 and PN, we take K as 2 and increase its value as long as the  area of the triangle (P1, PN, P(K+ 1)) is greater than the area of the triangle (P1, PN, P(K+ 1)) 
• Hence all the points between P1 and PK are lower hull while the rest are the upper hull.
• Set K as the midHull

Step 3: Finding the maximum distance points

• To find the maximum distance point, we can use two-pointers. We will create a lower and an upper pointer.
• We check if the area of the triangle is made by points (P(lower), P(lower+ 1), P(upper)) is greater than the area of the triangle made by the points (P(lower), P(lower+ 1), P(upper + 1)) if it’s true than increase the upper pointer otherwise increase the lower pointer.
  
   

We create a Point class with x and y attributes denoting (x, y) coordinate of the point.

We create getSquaredDistance(pointA, pointB), function, which will return squared distance between pointA, pointB.

We create a getCrossProduct(a, b, c) which will return the value of the cross product between the vectors formed by points ab and ac, i.e., it will return |ab X ac|

We create a function getConvexHull(points), which will return the convex hull of the given Point array, points, it will return convex hull in a counterclockwise direction.

Algorithm:

• In the class Point(x, y),
  • Set Point.x as x
  • Set Point.y as y
• In the function getSquaredDistance(pointA, pointB)
  • Return (pointA.x - pointB.x)^2 +( pointA.y - pointB.y)^2
• In the function getCrossProduct(a, b, c)
  • Return the cross product ((b.x - a.x)*(c.y - a.y)) - ((b.y - a.y)*(c.x - a.x))
• In the function getLowestPoint(points)
  • Set lowestPoint as points[0]
  • Iterate point through points
    • If point.y is lower than lowerPoint.y
      • Then set lowerPoint as point
    • Otherwise, if point.y is equal to lowerPoint.y and point.x is less than lowestPoint.x
      • Then set lowerPoint as point
  • Return the lowetPoint
• In the function getConvexHull(points)
  • Sort the points array based on the custom comparator comp
  • In comparator comp(point1, point2)
    • Set crossProduct as getCrossProductut(lowestPoint, point1, point2)
    • If crossProduct is 0
      • Return getSquaredDistance(pointA, lowestPoint) - getSquareDistance(pointB, lowestPoint)
    • Return crossProduct  multiplied by -1
  • Initialise an empty set st
  • Insert the points points[0] and point[1] in the set st
  • Set n as the size of points
  • Iterate i from 2 to n - 1
    • Set nextPoint as the top element of st.
    • Remove the top element of st
    • Set currentPoint as points[i]
    • While the size of st greater than 0 and getCrossProduct(st.top(), currentPoint, nextPoint ) is less than or equal to 0
      • Remove the top of st and set it equal to currentPoint
    • Insert currentPoint in st.
    • Insert nextPoint in st
  • Return st
• If n equals to 1 return 0
• Initialise an empty array of Points as points
• Iterate location through locations
  • Create a new instance of a Point as point, with x as locations[0] and y as location[1]
• Set covexHull as getConvexHull(points)
• Set num as the size of convexHull
• If num equal to 2
  • Then return square root of getSquaredDistance(convexHull[0], convexHull[1]) divided X
• Set midHull as 1
• While the absolute value of getCrossProduct(convexHull[num - 1], convexHull[0], convexHull[(midHull + 1)  %num]) is greater than the absolute value of getCrossProduct(convexHull[num - 1], convexHull[0], convexHull[midHull])
  • Increase K by 1
• Set lower as 0 and upper as midHull
• Set maxDistance as 0
• While lower is less than or equal to midHull and upper is greater than num
  • Set maxDistance as the maximum of maxDistance and getSquearedDistance(convexHull[lower], convexHull[upper])
  • If the absolute value of getCrossProduct(convexHull[lower], convexHull[(upper + 1) % num], convexHull[(lower + 1)  %num]) is greater than the absolute value of getCrossProduct(convexHull[lower], convexHull[upper], convexHull[(lower + 1) % num])
    • Increase upper by 1
  • Otherwise, increase lower by 1
• Set maxDistance as square root of maxDistance
• Set the float ans as maxDistance  divided by X
• Round ans to 6 floating points
• Finally, return ans