Given three 2-Dimensional vector co-ordinates A, B and C. The task is to perform below operations any number of times on vector A to get vector B :
- Rotate the vector 90 degrees clockwise.
- Add vector C to it.
Print “YES” B is obtained using the above operations, else Print “NO”.
Examples:
Input: Vector A: 2 3, Vector B: 2 3, Vector C: 0 0 Output: YES The given vector A has coordinate (2, 3) and we need to convert this vector A to vector B which is also (2, 3). By rotating vector A 4 times by 90 degrees and adding it to vector C(0, 0) will give us vector B(2, 3). Input: Vector A: 0 0, Vector B: 1 1, Vector C: 2 2 Output: NO
Below is the step by step algorithm to solve this problem:
- Initialize three vectors of 2-D coordinates as A ( a, b ), B ( x, y ) and C ( p, q ).
- Coordinates of vector A can be of any quadrant. So, initialize a check function for all the quadrant and check if any of it is true.
- Find a-x and b-y, which will tell us how much we need to make it to vector B.
- Initialize d = p*p + q*q. If d = 0 then you need not to add anything in vector A.
- If D > 0, then check if a*p + b*q and b*p – a*q is in the multiple of ‘d’ so that it is possible to get the vector B.
Below is the implementation of above algorithm:
C++
// C++ program to Check if it is// possible to reach vector B by// Rotating vector A and adding// vector C to it any number of times#include <bits/stdc++.h>using namespace std;#define ll long long// function to check if vector B is// possible from vector All check(ll a, ll b, ll p, ll q){ ll d = p * p + q * q; // if d = 0, then you need to add nothing to vector A if (d == 0) return a == 0 && b == 0; else return (a * p + b * q) % d == 0 && (b * p - a * q) % d == 0;}bool check(int a, int b, int x, int y, int p, int q){ // for all four quadrants if (check(a - x, b - y, p, q) || check(a + x, b + y, p, q) || check(a - y, b + x, p, q) || check(a + y, b - x, p, q)) return true; else return false;}// Driver codeint main(){ // initialize all three // vector coordinates int a = -4, b = -2; int x = 0, y = 0; int p = -2, q = -1; if (check(a, b, x, y, p, q)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java program to Check if it is // possible to reach vector B by // Rotating vector A and adding // vector C to it any number of times. public class GFG { // function to check if vector B is // possible from vector A static boolean check(long a, long b, long p, long q) { long d = p * p + q * q; // if d = 0, then you need to add nothing to vector A if (d == 0) return a == 0 && b == 0; else return (a * p + b * q) % d == 0 && (b * p - a * q) % d == 0; } static boolean check(int a, int b, int x, int y, int p, int q) { // for all four quadrants if (check(a - x, b - y, p, q) || check(a + x, b + y, p, q) || check(a - y, b + x, p, q) || check(a + y, b - x, p, q)) return true; else return false; } // Driver code public static void main(String args[]) { // initialize all three // vector coordinates int a = -4, b = -2; int x = 0, y = 0; int p = -2, q = -1; if (check(a, b, x, y, p, q)) System.out.println("Yes"); else System.out.println("No"); } // This Code is contributed by ANKITRAI1} |
Python3
# Python3 program to Check if it # is possible to reach vector B # by Rotating vector A and adding# vector C to it any number of times# function to check if vector B # is possible from vector Adef check(a, b, p, q): d = p * p + q * q; # if d = 0, then you need to # add nothing to vector A if (d == 0): return a == 0 and b == 0; else : return ((a * p + b * q) % d == 0 and (b * p - a * q) % d == 0);def checks(a, b, x, y, p, q): # for all four quadrants if (check(a - x, b - y, p, q) or check(a + x, b + y, p, q) or check(a - y, b + x, p, q) or check(a + y, b - x, p, q)): return True; else: return False;# Driver code# initialize all three# vector coordinatesa = -4;b = -2;x = 0;y = 0;p = -2;q = -1;if (checks(a, b, x, y, p, q)): print( "Yes");else: print ("No");# This code is contributed# by Shivi_Aggarwal |
C#
// C# program to Check if it is // possible to reach vector B by // Rotating vector A and adding // vector C to it any number of times.using System;class GFG {// function to check if vector B is // possible from vector A static bool check(long a, long b, long p, long q) { long d = p * p + q * q; // if d = 0, then you need to // add nothing to vector A if (d == 0) return a == 0 && b == 0; else return (a * p + b * q) % d == 0 && (b * p - a * q) % d == 0; } static bool check(int a, int b, int x, int y, int p, int q) { // for all four quadrants if (check(a - x, b - y, p, q) || check(a + x, b + y, p, q) || check(a - y, b + x, p, q) || check(a + y, b - x, p, q)) return true; else return false; } // Driver codepublic static void Main(){ // initialize all three // vector coordinates int a = -4, b = -2; int x = 0, y = 0; int p = -2, q = -1; if (check(a, b, x, y, p, q)) Console.Write("Yes"); else Console.Write("No"); }}// This code is contributed// by ChitraNayal |
PHP
<?php// PHP program to Check if it is// possible to reach vector B by// Rotating vector A and adding// vector C to it any number of times// function to check if vector B is// possible from vector Afunction check($a, $b, $p, $q){ $d = $p * $p + $q * $q; // if d = 0, then you need to add nothing to vector A if ($d == 0) return ( $a == 0 && $b == 0); else return (($a * $p + $b * $q) % $d == 0 && ($b * $p - $a * $q) % $d == 0);}function check1($a, $b, $x, $y, $p, $q){ // for all four quadrants if (check($a - $x, $b - $y, $p, $q) || check($a + $x, $b + $y, $p, $q) || check($a - $y, $b + $x, $p, $q) || check($a + $y, $b - $x, $p, $q)) return true; else return false;}// Driver code // initialize all three // vector coordinates $a = -4; $b = -2; $x = 0; $y = 0; $p = -2; $q = -1; if (check1($a, $b, $x, $y, $p, $q)) echo "Yes"; else echo "No";// This Code is contributed by mits?> |
Javascript
<script>// Javascript program to Check if it is // possible to reach vector B by // Rotating vector A and adding // vector C to it any number of times.// Function to check if vector B is // possible from vector A function _check(a, b, p, q) { var d = p * p + q * q; // If d = 0, then you need // to add nothing to vector A if (d == 0) return a == 0 && b == 0; else return (a * p + b * q) % d == 0 && (b * p - a * q) % d == 0; } function check(a, b, x, y, p, q) { // for all four qua // for all four quadrants if (_check(a - x, b - y, p, q) || _check(a + x, b + y, p, q) || _check(a - y, b + x, p, q) || _check(a + y, b - x, p, q)) return true; else return false; } // Driver code// Initialize all three // vector coordinates var a = -4, b = -2; var x = 0, y = 0; var p = -2, q = -1; if (check(a, b, x, y, p, q)) document.write("Yes"); else document.write("No"); // This code is contributed by Kirti</script> |
Output:
Yes
Time Complexity: O(1)
Auxiliary space: O(1)
Take a part in the ongoing discussion
