Given three coordinates of a triangle (x1, y1), (x2, y2), (x3, y3). The task is to find out if the triangle can be transformed to a right-angled triangle by moving only one point exactly by the distance 1.
If it is possible to make the triangle right-angled, then print “POSSIBLE”, else print “NOT POSSIBLE”.
If the triangle is already right-angled, it should also be reported.
Examples:
Input:
x1 = -1, y1 = 0
x2 = 2, y2 = 0
x3 = 0, y3 = 1
Output: POSSIBLE
First co-ordinate (-1, 0) can be changed to (0, 0) and make it right-angled.
Input:
x1 = 36, y1 = 1
x2 = -17, y2 = -54
x3 = -19, y3 = 55
Output: POSSIBLE
Approach:
As it is known that for a triangle of sides a, b and c, the triangle will be right-angled if the following equation holds true : a2 + b2 = c2
So for every co-ordinates of the triangle, find out all the sides and for the 3 possible permutations of them check if it is already right-angle triangle and report it.
If the above condition doesn’t hold true, then the following operations need to be done-
We need to change all the co-ordinates by 1 one by one and check that is it a valid combination for a right-angled triangle.
Look that there can be 4 possible combinations to change every co-ordinates by 1. They are (-1, 0), (0, 1), (1, 0), (0, -1). So run a loop and apply those changes one by one for every co-ordinates and check that the formula a2 + b2 = c2 is true or not.
If it’s true then it is possible to transform the triangle to a right-angled triangle, otherwise not.
Below is the implementation of the above code:
C++
// C++ implementation of// the above approach#include <bits/stdc++.h>using namespace std;// Storing all the possible// changes to make the triangle// right-angledint dx[] = { -1, 0, 1, 0 };int dy[] = { 0, 1, 0, -1 };// Function to check if the triangle// is right-angled or notint ifRight(int x1, int y1, int x2, int y2, int x3, int y3){ int a = ((x1 - x2) * (x1 - x2)) + ((y1 - y2) * (y1 - y2)); int b = ((x1 - x3) * (x1 - x3)) + ((y1 - y3) * (y1 - y3)); int c = ((x2 - x3) * (x2 - x3)) + ((y2 - y3) * (y2 - y3)); if ((a == (b + c) && a != 0 && b != 0 && c != 0) || (b == (a + c) && a != 0 && b != 0 && c != 0) || (c == (a + b) && a != 0 && b != 0 && c != 0)) { return 1; } return 0;}// Function to check if the triangle// can be transformed to right-angledvoid isValidCombination(int x1, int y1, int x2, int y2, int x3, int y3){ int x, y; // Boolean variable to // return true or false bool possible = 0; // If it is already right-angled if (ifRight(x1, y1, x2, y2, x3, y3)) { cout << "ALREADY RIGHT ANGLED"; return; } else { // Applying the changes on the // co-ordinates for (int i = 0; i < 4; i++) { // Applying on the first // co-ordinate x = dx[i] + x1; y = dy[i] + y1; if (ifRight(x, y, x2, y2, x3, y3)) { cout << "POSSIBLE"; return; } // Applying on the second // co-ordinate x = dx[i] + x2; y = dy[i] + y2; if (ifRight(x1, y1, x, y, x3, y3)) { cout << "POSSIBLE"; return; } // Applying on the third // co-ordinate x = dx[i] + x3; y = dy[i] + y3; if (ifRight(x1, y1, x2, y2, x, y)) { cout << "POSSIBLE"; return; } } } // If can't be transformed if (!possible) cout << "NOT POSSIBLE" << endl;}// Driver Codeint main(){ int x1 = -49, y1 = 0; int x2 = 0, y2 = 50; int x3 = 0, y3 = -50; isValidCombination(x1, y1, x2, y2, x3, y3); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{// Storing all the possible// changes to make the triangle// right-angledstatic int dx[] = { -1, 0, 1, 0 };static int dy[] = { 0, 1, 0, -1 };// Function to check if the triangle// is right-angled or notstatic boolean ifRight(int x1, int y1, int x2, int y2, int x3, int y3){ int a = ((x1 - x2) * (x1 - x2)) + ((y1 - y2) * (y1 - y2)); int b = ((x1 - x3) * (x1 - x3)) + ((y1 - y3) * (y1 - y3)); int c = ((x2 - x3) * (x2 - x3)) + ((y2 - y3) * (y2 - y3)); if ((a == (b + c) && a != 0 && b != 0 && c != 0) || (b == (a + c) && a != 0 && b != 0 && c != 0) || (c == (a + b) && a != 0 && b != 0 && c != 0)) { return true; } return false;}// Function to check if the triangle// can be transformed to right-angledstatic void isValidCombination(int x1, int y1, int x2, int y2, int x3, int y3){ int x, y; // Boolean variable to // return true or false boolean possible = false; // If it is already right-angled if (ifRight(x1, y1, x2, y2, x3, y3)) { System.out.print("ALREADY RIGHT ANGLED"); return; } else { // Applying the changes on the // co-ordinates for (int i = 0; i < 4; i++) { // Applying on the first // co-ordinate x = dx[i] + x1; y = dy[i] + y1; if (ifRight(x, y, x2, y2, x3, y3)) { System.out.print("POSSIBLE"); return; } // Applying on the second // co-ordinate x = dx[i] + x2; y = dy[i] + y2; if (ifRight(x1, y1, x, y, x3, y3)) { System.out.print("POSSIBLE"); return; } // Applying on the third // co-ordinate x = dx[i] + x3; y = dy[i] + y3; if (ifRight(x1, y1, x2, y2, x, y)) { System.out.print("POSSIBLE"); return; } } } // If can't be transformed if (!possible) System.out.println("NOT POSSIBLE");}// Driver Codepublic static void main(String[] args) { int x1 = -49, y1 = 0; int x2 = 0, y2 = 50; int x3 = 0, y3 = -50; isValidCombination(x1, y1, x2, y2, x3, y3);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the above approach# Storing all the possible# changes to make the triangle# right-angleddx = [-1, 0, 1, 0]dy = [0, 1, 0, -1]# Function to check if the triangle# is right-angled or notdef ifRight(x1, y1, x2, y2, x3, y3): a = ((x1 - x2) * (x1 - x2)) + \ ((y1 - y2) * (y1 - y2)) b = ((x1 - x3) * (x1 - x3)) + \ ((y1 - y3) * (y1 - y3)) c = ((x2 - x3) * (x2 - x3)) + \ ((y2 - y3) * (y2 - y3)) if ((a == (b + c) and a != 0 and b != 0 and c != 0) or (b == (a + c) and a != 0 and b != 0 and c != 0) or (c == (a + b) and a != 0 and b != 0 and c != 0)): return 1# Function to check if the triangle# can be transformed to right-angleddef isValidCombination(x1, y1, x2, y2, x3, y3): x, y = 0, 0 # Boolean variable to # return true or false possible = 0 # If it is already right-angled if (ifRight(x1, y1, x2, y2, x3, y3)): print("ALREADY RIGHT ANGLED") return else: # Applying the changes on the # co-ordinates for i in range(4): # Applying on the first # co-ordinate x = dx[i] + x1 y = dy[i] + y1 if (ifRight(x, y, x2, y2, x3, y3)): print("POSSIBLE") return # Applying on the second # co-ordinate x = dx[i] + x2 y = dy[i] + y2 if (ifRight(x1, y1, x, y, x3, y3)): print("POSSIBLE") return # Applying on the third # co-ordinate x = dx[i] + x3 y = dy[i] + y3 if (ifRight(x1, y1, x2, y2, x, y)): print("POSSIBLE") return # If can't be transformed if (possible == 0): print("NOT POSSIBLE")# Driver Codex1 = -49y1 = 0x2 = 0y2 = 50x3 = 0y3 = -50isValidCombination(x1, y1, x2, y2, x3, y3)# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approach using System;class GFG { // Storing all the possible // changes to make the triangle // right-angled static int []dx = { -1, 0, 1, 0 }; static int []dy = { 0, 1, 0, -1 }; // Function to check if the triangle // is right-angled or not static bool ifRight(int x1, int y1, int x2, int y2, int x3, int y3) { int a = ((x1 - x2) * (x1 - x2)) + ((y1 - y2) * (y1 - y2)); int b = ((x1 - x3) * (x1 - x3)) + ((y1 - y3) * (y1 - y3)); int c = ((x2 - x3) * (x2 - x3)) + ((y2 - y3) * (y2 - y3)); if ((a == (b + c) && a != 0 && b != 0 && c != 0) || (b == (a + c) && a != 0 && b != 0 && c != 0) || (c == (a + b) && a != 0 && b != 0 && c != 0)) { return true; } return false; } // Function to check if the triangle // can be transformed to right-angled static void isValidCombination(int x1, int y1, int x2, int y2, int x3, int y3) { int x, y; // Boolean variable to // return true or false bool possible = false; // If it is already right-angled if (ifRight(x1, y1, x2, y2, x3, y3)) { Console.WriteLine("ALREADY RIGHT ANGLED"); return; } else { // Applying the changes on the // co-ordinates for (int i = 0; i < 4; i++) { // Applying on the first // co-ordinate x = dx[i] + x1; y = dy[i] + y1; if (ifRight(x, y, x2, y2, x3, y3)) { Console.WriteLine("POSSIBLE"); return; } // Applying on the second // co-ordinate x = dx[i] + x2; y = dy[i] + y2; if (ifRight(x1, y1, x, y, x3, y3)) { Console.WriteLine("POSSIBLE"); return; } // Applying on the third // co-ordinate x = dx[i] + x3; y = dy[i] + y3; if (ifRight(x1, y1, x2, y2, x, y)) { Console.Write("POSSIBLE"); return; } } } // If can't be transformed if (!possible) Console.WriteLine("NOT POSSIBLE"); } // Driver Code static public void Main () { int x1 = -49, y1 = 0; int x2 = 0, y2 = 50; int x3 = 0, y3 = -50; isValidCombination(x1, y1, x2, y2, x3, y3); } }// This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript implementation of// the above approach// Storing all the possible// changes to make the triangle// right-angledlet dx = [ -1, 0, 1, 0 ];let dy = [ 0, 1, 0, -1 ];// Function to check if the triangle// is right-angled or notfunction ifRight(x1, y1, x2, y2, x3, y3){ let a = ((x1 - x2) * (x1 - x2)) + ((y1 - y2) * (y1 - y2)); let b = ((x1 - x3) * (x1 - x3)) + ((y1 - y3) * (y1 - y3)); let c = ((x2 - x3) * (x2 - x3)) + ((y2 - y3) * (y2 - y3)); if ((a == (b + c) && a != 0 && b != 0 && c != 0) || (b == (a + c) && a != 0 && b != 0 && c != 0) || (c == (a + b) && a != 0 && b != 0 && c != 0)) { return 1; } return 0;}// Function to check if the triangle// can be transformed to right-angledfunction isValidCombination(x1, y1, x2, y2, x3, y3){ let x, y; // Boolean variable to // return true or false let possible = 0; // If it is already right-angled if (ifRight(x1, y1, x2, y2, x3, y3)) { document.write("ALREADY RIGHT ANGLED"); return; } else { // Applying the changes on the // co-ordinates for (let i = 0; i < 4; i++) { // Applying on the first // co-ordinate x = dx[i] + x1; y = dy[i] + y1; if (ifRight(x, y, x2, y2, x3, y3)) { document.write("POSSIBLE"); return; } // Applying on the second // co-ordinate x = dx[i] + x2; y = dy[i] + y2; if (ifRight(x1, y1, x, y, x3, y3)) { document.write("POSSIBLE"); return; } // Applying on the third // co-ordinate x = dx[i] + x3; y = dy[i] + y3; if (ifRight(x1, y1, x2, y2, x, y)) { document.write("POSSIBLE"); return; } } } // If can't be transformed if (!possible) document.write("NOT POSSIBLE<br>");}// Driver Code let x1 = -49, y1 = 0; let x2 = 0, y2 = 50; let x3 = 0, y3 = -50; isValidCombination(x1, y1, x2, y2, x3, y3);</script> |
Output:
POSSIBLE
Time Complexity: O(1)
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!
