Given N points on the plane, ( X1, Y1 ), ( X2, Y2 ), ( X3, Y3 ), ……, ( XN, YN ). The task is to calculate the minimum length of the shorter side of the triangle. and the path or points to place an isosceles triangle with any two sides of the triangle on the coordinate axis ( X axis and Y axis ) to cover all points.
Note: A point is covered if it lies inside the triangle or on the side of the triangle.
Examples:
Input: (1, 3), (1, 1), (2, 1), (2, 2)
Output: Length -> 4 , Path -> ( 1, 4 ) and ( 4, 1 )
Input: (1, 2), (1, 1), (2, 1)
Output: Length -> 3 , Path -> ( 1, 3 ) and ( 3, 1 )
In the first example, the minimum length of the shortest path is equal to the maximum sum of the points, which is 1+3 or 2+2. So the path which will cover all the points is (1, 4) and (4, 1) on the coordinate axis.
Below is the step by step algorithm to solve this problem:
- Initialize ‘N’ points on a plane.
- Traverse through each point and find the sum of each point and store it in a variable ‘answer’.
- Replace the next maximum sum of the points with the previous sum.
- Then you will get the path on a coordinate axis ( 1, answer ) and ( answer, 1 ) which will cover all the points of isosceles triangle.
Below is the implementation of above algorithm:
C++
// C++ program to illustrate// the above problem#include <bits/stdc++.h>using namespace std;#define ll long long// function to get the minimum length of// the shorter side of the trianglevoid shortestLength(int n, int x[], int y[]){ int answer = 0; // traversing through each points on the plane int i = 0; while (n--) { // if sum of a points is greater than the // previous one, the maximum gets replaced if (x[i] + y[i] > answer) answer = x[i] + y[i]; i++; } // print the length cout << "Length -> " << answer << endl; cout << "Path -> " << "( 1, " << answer << " )" << "and ( " << answer << ", 1 )";}// Driver codeint main(){ // initialize the number of points int n = 4; // points on the plane int x[n] = { 1, 4, 2, 1 }; int y[n] = { 4, 1, 1, 2 }; shortestLength(n, x, y); return 0;} |
Java
// Java program to illustrate // the above problem class GFG{// function to get the minimum length of // the shorter side of the triangle static void shortestLength(int n, int x[], int y[]) { int answer = 0; // traversing through each // points on the plane int i = 0; while (n != 0 && i < x.length) { // if sum of a points is greater // than the previous one, the // maximum gets replaced if (x[i] + y[i] > answer) answer = x[i] + y[i]; i++; } // print the length System.out.println("Length -> " + answer ); System.out.println("Path -> " + "( 1, " + answer + " )" + "and ( " + answer + ", 1 )"); } // Driver code public static void main(String[] args) { // initialize the number of points int n = 4; // points on the plane int x[] = new int[] { 1, 4, 2, 1 }; int y[] = new int[] { 4, 1, 1, 2 }; shortestLength(n, x, y); } }// This code is contributed // by Prerna Saini |
Python 3
# Python 3 program to illustrate# the above problem# function to get the minimum length of# the shorter side of the triangledef shortestLength(n, x, y): answer = 0 # traversing through each # points on the plane i = 0 while n > 0: # if sum of a points is greater # than the previous one, the # maximum gets replaced if (x[i] + y[i] > answer): answer = x[i] + y[i] i += 1 n -= 1 # print the length print("Length -> "+ str(answer)) print( "Path -> "+ "( 1, " +str(answer)+ " )"+ "and ( "+str( answer) +", 1 )")# Driver codeif __name__ == "__main__": # initialize the number of points n = 4 # points on the plane x = [ 1, 4, 2, 1 ] y = [ 4, 1, 1, 2 ] shortestLength(n, x, y)# This code is contributed # by ChitraNayal |
C#
// C# program to illustrate // the above problem using System;class GFG{// function to get the minimum // length of the shorter side // of the triangle static void shortestLength(int n, int[] x, int[] y) { int answer = 0; // traversing through each // points on the plane int i = 0; while (n != 0 && i < x.Length) { // if sum of a points is greater // than the previous one, the // maximum gets replaced if (x[i] + y[i] > answer) answer = x[i] + y[i]; i++; } // print the length Console.WriteLine("Length -> " + answer); Console.WriteLine("Path -> " + "( 1, " + answer + " )" + "and ( " + answer + ", 1 )"); } // Driver codestatic public void Main (){ // initialize the // number of points int n = 4; // points on the plane int[] x = new int[] { 1, 4, 2, 1 }; int[] y = new int[] { 4, 1, 1, 2 }; shortestLength(n, x, y); }}// This code is contributed by Mahadev |
PHP
<?php // PHP program to illustrate// the above problem// function to get the minimum length of// the shorter side of the trianglefunction shortestLength($n, &$x, &$y){ $answer = 0; // traversing through each // points on the plane $i = 0; while ($n--) { // if sum of a points is greater // than the previous one, the // maximum gets replaced if ($x[$i] + $y[$i] > $answer) $answer = $x[$i] + $y[$i]; $i++; } // print the length echo "Length -> ".$answer."\n"; echo "Path -> ". "( 1, " .$answer ." )". "and ( " .$answer . ", 1 )";}// Driver code// initialize the number of points$n = 4;// points on the plane$x = array(1, 4, 2, 1 );$y = array(4, 1, 1, 2 );shortestLength($n, $x, $y);// This code is contributed // by ChitraNayal?> |
Javascript
<script>// Javascript program to illustrate // the above problem // function to get the minimum length of // the shorter side of the triangle function shortestLength(n, x, y) { let answer = 0; // traversing through each // points on the plane let i = 0; while (n != 0 && i < x.length) { // if sum of a points is greater // than the previous one, the // maximum gets replaced if (x[i] + y[i] > answer) answer = x[i] + y[i]; i++; } // print the length document.write("Length -> " + answer + "<br/>"); document.write("Path -> " + "( 1, " + answer + " )" + "and ( " + answer + ", 1 )"); } // Driver Code // initialize the number of points let n = 4; // points on the plane let x = [ 1, 4, 2, 1 ]; let y = [ 4, 1, 1, 2 ]; shortestLength(n, x, y); </script> |
Output:
Length -> 5 Path -> ( 1, 5 )and ( 5, 1 )
Time Complexity: O(n) where n is the number of points.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
