Given three points on the x-y coordinate plane. You need to find the no. of line segments formed by making a polyline passing through these points. (Line segment can be vertically or horizontally aligned to the coordinate axis)
Examples :
Input : A = {-1, -1}, B = {-1, 3}, C = {4, 3} Output : 2 Expantaion:
There are two segments in this polyline. Input :A = {1, 1}, B = {2, 3} C = {3, 2} Output : 3
The result is one if all points are on x axis or y axis. The result is 2 if points can form L shape. L shape is formed if any of the three points can be used as a joining point. Otherwise answer is 3.
C++
// CPP program to find number of horizontal (or vertical // line segments needed to connect three points. #include <iostream> using namespace std; // Function to check if the third point forms a // rectangle with other two points at corners bool isBetween( int a, int b, int c) { return min(a, b) <= c && c <= max(a, b); } // Returns true if point k can be used as a joining // point to connect using two line segments bool canJoin( int x[], int y[], int i, int j, int k) { // Check for the valid polyline with two segments return (x[k] == x[i] || x[k] == x[j]) && isBetween(y[i], y[j], y[k]) || (y[k] == y[i] || y[k] == y[j]) && isBetween(x[i], x[j], x[k]); } int countLineSegments( int x[], int y[]) { // Check whether the X-coordinates or // Y-cocordinates are same. if ((x[0] == x[1] && x[1] == x[2]) || (y[0] == y[1] && y[1] == y[2])) return 1; // Iterate over all pairs to check for two // line segments else if (canJoin(x, y, 0, 1, 2) || canJoin(x, y, 0, 2, 1) || canJoin(x, y, 1, 2, 0)) return 2; // Otherwise answer is three. else return 3; } // Driver code int main() { int x[3], y[3]; x[0] = -1; y[0] = -1; x[1] = -1; y[1] = 3; x[2] = 4; y[2] = 3; cout << countLineSegments(x, y); return 0; } |
Java
// Java program to find number of horizontal // (or vertical line segments needed to // connect three points. import java.io.*; class GFG { // Function to check if the third // point forms a rectangle with // other two points at corners static boolean isBetween( int a, int b, int c) { return (Math.min(a, b) <= c && c <= Math.max(a, b)); } // Returns true if point k can be // used as a joining point to connect // using two line segments static boolean canJoin( int x[], int y[], int i, int j, int k) { // Check for the valid polyline // with two segments return (x[k] == x[i] || x[k] == x[j]) && isBetween(y[i], y[j], y[k]) || (y[k] == y[i] || y[k] == y[j]) && isBetween(x[i], x[j], x[k]); } static int countLineSegments( int x[], int y[]) { // Check whether the X-coordinates or // Y-cocordinates are same. if ((x[ 0 ] == x[ 1 ] && x[ 1 ] == x[ 2 ]) || (y[ 0 ] == y[ 1 ] && y[ 1 ] == y[ 2 ])) return 1 ; // Iterate over all pairs to check for two // line segments else if (canJoin(x, y, 0 , 1 , 2 ) || canJoin(x, y, 0 , 2 , 1 ) || canJoin(x, y, 1 , 2 , 0 )) return 2 ; // Otherwise answer is three. else return 3 ; } // Driver code public static void main (String[] args) { int x[]= new int [ 3 ], y[]= new int [ 3 ]; x[ 0 ] = - 1 ; y[ 0 ] = - 1 ; x[ 1 ] = - 1 ; y[ 1 ] = 3 ; x[ 2 ] = 4 ; y[ 2 ] = 3 ; System.out.println(countLineSegments(x, y)); } } // This code is contributed by vt_m |
Python3
# Python program to find number # of horizontal (or vertical # line segments needed to # connect three points. import math # Function to check if the # third point forms a # rectangle with other # two points at corners def isBetween(a, b, c) : return min (a, b) < = c and c < = max (a, b) # Returns true if point k # can be used as a joining # point to connect using # two line segments def canJoin( x, y, i, j, k) : # Check for the valid polyline # with two segments return (x[k] = = x[i] or x[k] = = x[j]) and isBetween(y[i], y[j], y[k]) or (y[k] = = y[i] or y[k] = = y[j]) and isBetween(x[i], x[j], x[k]) def countLineSegments( x, y): # Check whether the X-coordinates or # Y-cocordinates are same. if ((x[ 0 ] = = x[ 1 ] and x[ 1 ] = = x[ 2 ]) or (y[ 0 ] = = y[ 1 ] and y[ 1 ] = = y[ 2 ])): return 1 # Iterate over all pairs to check for two # line segments elif (canJoin(x, y, 0 , 1 , 2 ) or canJoin(x, y, 0 , 2 , 1 ) or canJoin(x, y, 1 , 2 , 0 )): return 2 # Otherwise answer is three. else : return 3 #driver code x = [ - 1 , - 1 , 4 ] y = [ - 1 , 3 , 3 ] print (countLineSegments(x, y)) # This code is contributed by Gitanjali. |
C#
// C# program to find number of horizontal // (or vertical) line segments needed to // connect three points. using System; class GFG { // Function to check if the third // point forms a rectangle with // other two points at corners static bool isBetween( int a, int b, int c) { return (Math.Min(a, b) <= c && c <= Math.Max(a, b)); } // Returns true if point k can be // used as a joining point to connect // using two line segments static bool canJoin( int [] x, int [] y, int i, int j, int k) { // Check for the valid polyline // with two segments return (x[k] == x[i] || x[k] == x[j]) && isBetween(y[i], y[j], y[k]) || (y[k] == y[i] || y[k] == y[j]) && isBetween(x[i], x[j], x[k]); } static int countLineSegments( int [] x, int [] y) { // Check whether the X-coordinates or // Y-cocordinates are same. if ((x[0] == x[1] && x[1] == x[2]) || (y[0] == y[1] && y[1] == y[2])) return 1; // Iterate over all pairs to check for two // line segments else if (canJoin(x, y, 0, 1, 2) || canJoin(x, y, 0, 2, 1) || canJoin(x, y, 1, 2, 0)) return 2; // Otherwise answer is three. else return 3; } // Driver code public static void Main() { int [] x = new int [3]; int [] y = new int [3]; x[0] = -1; y[0] = -1; x[1] = -1; y[1] = 3; x[2] = 4; y[2] = 3; Console.WriteLine(countLineSegments(x, y)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to find number // of horizontal (or vertical // line segments needed to // connect three points. // Function to check if the // third point forms a // rectangle with other // two points at corners function isBetween( $a , $b , $c ) { return min( $a , $b ) <= $c and $c <= max( $a , $b ); } // Returns true if point k // can be used as a joining // point to connect using // two line segments function canJoin( $x , $y , $i , $j , $k ) { // Check for the valid // polyline with two segments return ( $x [ $k ] == $x [ $i ] or $x [ $k ] == $x [ $j ]) and isBetween( $y [ $i ], $y [ $j ], $y [ $k ]) or ( $y [ $k ] == $y [ $i ] or $y [ $k ] == $y [ $j ]) and isBetween( $x [ $i ], $x [ $j ], $x [ $k ]); } function countLineSegments( $x , $y ) { // Check whether the X-coordinates // or Y-cocordinates are same. if (( $x [0] == $x [1] and $x [1] == $x [2]) or ( $y [0] == $y [1] and $y [1] == $y [2])) return 1; // Iterate over all pairs to // check for two line segments else if (canJoin( $x , $y , 0, 1, 2) or canJoin( $x , $y , 0, 2, 1) || canJoin( $x , $y , 1, 2, 0)) return 2; // Otherwise answer is three. else return 3; } // Driver code $x = array (); $y = array (); $x [0] = -1; $y [0] = -1; $x [1] = -1; $y [1] = 3; $x [2] = 4; $y [2] = 3; echo countLineSegments( $x , $y ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // JavaScript program to find number of horizontal // (or vertical line segments needed to // connect three points. // Function to check if the third // point forms a rectangle with // other two points at corners function isBetween(a, b, c) { return (Math.min(a, b) <= c && c <= Math.max(a, b)); } // Returns true if point k can be // used as a joining point to connect // using two line segments function canJoin(x, y, i, j, k) { // Check for the valid polyline // with two segments return (x[k] == x[i] || x[k] == x[j]) && isBetween(y[i], y[j], y[k]) || (y[k] == y[i] || y[k] == y[j]) && isBetween(x[i], x[j], x[k]); } function countLineSegments(x, y) { // Check whether the X-coordinates or // Y-cocordinates are same. if ((x[0] == x[1] && x[1] == x[2]) || (y[0] == y[1] && y[1] == y[2])) return 1; // Iterate over all pairs to check for two // line segments else if (canJoin(x, y, 0, 1, 2) || canJoin(x, y, 0, 2, 1) || canJoin(x, y, 1, 2, 0)) return 2; // Otherwise answer is three. else return 3; } // Driver code let x = [], y = []; x[0] = -1; y[0] = -1; x[1] = -1; y[1] = 3; x[2] = 4; y[2] = 3; document.write(countLineSegments(x, y)); </script> |
Output :
2
Time Complexity : O(1) ,as we are not using any loop in program.
Space Complexity : O(1) ,as we are not using any extra space.
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!