Checks whether it is possible to reach any point on the circumference of a given circle from the origin

The circumference of a circle can be defined as the outer boundary of the circle. It is the circumference of the circle. Every point around the circle follows certain properties as shown below -

• Point (x,y) is located inside the circle such that $\mathrm{x^2 y^2

• Point (x,y) is located on the circle such that $\mathrm{x^2 y^2 = R^2}$

• Point (x,y) is located outside the circle, such that $\mathrm{x^2 y^2 > R^2}$

Where R = radius of the circle.

Problem Statement

Given a string S representing a series of moves (L, R, U, D) and an integer R representing the radius of a circle. Check whether any point on the circumference of a circle of radius R with the origin can be reached by selecting any subsequence of moves starting from S. The operation of each move is as follows,

• L = Decrease x coordinate

• R = incremental x coordinate

• U = y coordinate increment

• D = Decrementing y coordinate

Example 1

enter

S = “RURDLR”
R = 2

Output

yes

illustrate

Select subsequence "RR" -

Initially, (0, 0) R -> (1, 0) R -> (2, 0).

Perimeter may be 2² 02 = 4 = R²

Example 2

enter

S = “UUUUU”
R = 6

Output

no

illustrate

Select the largest subsequence "UUUU" -

Initially, (0, 0) U -> (0, 1) U -> (0, 2) U -> (0, 3) U -> (0, 4) U -> (0, 5) .

It is impossible to reach the circumference because 0² 5² = 25 R²

Method 1: Brute force cracking

The solution to the problem is to find all possible subsequences of the string S and then check whether each subsequence can reach the circle. These conditions are checked by maintaining counters for x and y, where x is decremented on each L and incremented on each R. Similarly, y decreases on every D and increases on every U. Then check x² y² = R² to check if the end point is on the circumference.

pseudocode

procedure subsequence (S, sub, vec):
   if S is empty
      add sub to vec
      return
   end if
   subsequence(S.substring(1), sub + S[0], vec)
   subsequence(S.substring(1), sub, vec)
end procedure

procedure checkSeq (S, R)
   x = 0
   y = 0
   for move in S do
      if move == 'L' then
         x = x - 1
      else if move == 'R' then
         x = x + 1
      else if move == 'U' then
         y = y + 1
      else if move == 'D' then
         y = y - 1
      end if
      if x^2 + y^2 = R^2 then
         return true
      end if
   end for
   return false
end procedure

procedure reachCircumference (S, R):
   v = []      
   subsequence(S, "", v)
   for str in v:
      if checkSeq(str, R)
      return "yes"
      end if
   return "no"
end procedure

Example: C implementation

In the following program, create all possible subsequences of the string S and check whether they reach the circumference of the circle.

#include <bits/stdc++.h>
using namespace std;

// Function to create all the possible subsequence of string S
void subsequence(string S, string sub, vector<string> &vec){

   // Base Case
   if (S.empty()) {
      vec.push_back(sub);
      return;
   }
   
   // Subsequence including the character
   subsequence(S.substr(1), sub + S[0], vec);
   
   // Subsequence excluding the character
   subsequence(S.substr(1), sub, vec);
}

// Function to check if a given sequence of steps lead to the circumference of the circle with radius R
bool checkSeq(string S, int R){

   // Initialising centre of circle as (0, 0)
   int x = 0, y = 0;
   for (char move : S) {
      if (move == 'L') {
         x -= 1;
      } else if (move == 'R') {
         x += 1;
      } else if (move == 'U') {
         y += 1;
      } else if (move == 'D') {
         y -= 1;
      }
      
      // Check to find if (x, y) lie on circumference using the circle equation
      if (x*x + y*y == R*R) {
         return true;
      }
   }
   return false;
}

// function to check if any subsequence of string S leads to any point on the circumference of the circle
string reachCircumference(string S, int R){
   vector <string> v;
   string sub = "";
   
   // Storing all subsequence in vector v
   subsequence(S, sub, v);
   
   // Checking the condition for each subsequence
   for (auto str: v) {
      if(checkSeq(str, R)) {
         return "yes";
         break;
      }
   }
   return "no";
}

// Driver Code
int main(){
   string S = "RURDLR";
   int R = 2;
   cout << reachCircumference(S, R) << endl;
   return 0;
}

Output

yes

Method 2: Optimization method

An efficient way to solve this problem is to check whether the sum of the squares of x and y is equal to the square of the radius for any pair of x and y using (L, R, U or D).

First, we count the maximum number of occurrences of each step and check if any of them are equal to R. If not equal, then we check whether any number of pairs of L or R and U or D can result in a distance origin equal to R .

pseudocode

procedure reachCircumference (S, R)
   cL = 0
   cR = 0
   cD = 0
   cU = 0
   for move in S do
if move == 'L' then
x = x - 1
else if move == 'R' then
x = x + 1
else if move == 'U' then
y = y + 1
else if move == 'D' then
y = y - 1
end if
if x^2 + y^2 = R^2 then
return true
end if
end for
   if max(max(cL, cR), max(cD, cU)) >= R
      return “yes”
   maxLR = max(cL, cR)
maxUD = max(cU, cD)
Initialise unordered map mp
sq = R * R
for i = 1 till i * i = sq
   if sq - i*i is not in the map
      if maxLR>= mp[sq - i * i] and maxUD >= i
         return “yes”
      end if
      if maxLR >= i && maxUD >= mp[sq - i * i]
         return “yes”
      end if
   end if
end for
return “no”
end procedure

The following is the C implementation,

In the following program, we use a map to check whether there is a subsequence leading to the circumference of a circle.

#include <bits/stdc++.h>
using namespace std;

// Function to check if any subsequence of string S leads to any point on the circumference of the circle
string reachCircumference (string S, int R){

   // Counting total occurrenceof each L, R, U, D
   int cL = 0, cR = 0, cD = 0, cU = 0;
   for (char move : S) {
      if (move == 'L') {
         cL++;
      } else if (move == 'R') {
         cR++;
      } else if (move == 'U') {
         cU++;
      } else if (move == 'D') {
         cD++;
      }
   }
   
   // Checking for a path to circumference using only one type of move
   if (max(max(cL, cR), max(cD, cU)) >= R) {
      return "yes";
   }
   int maxLR = max(cL, cR), maxUD = max(cU, cD);
   unordered_map<int, int> mp;
   int sq = R * R;
   for (int i = 1; i * i <= sq; i++) {
      mp[i * i] = i;
      if (mp.find(sq - i * i) != mp.end()) {
      
         // Checking if it is possible to reach (± mp[r_square - i*i], ± i)
         if (maxLR>= mp[sq - i * i] && maxUD >= i)
            return "yes";
            
         // Checking if it is possible to reach (±i, ±mp[r_square-i*i])
         if (maxLR >= i && maxUD >= mp[sq - i * i])
            return "yes";
      }
   }
   return "no";
}

// Driver Code
int main(){
   string S = "RURDLR";
   int R = 5;
   cout << reachCircumference(S, R) << endl;
   return 0;
}

Output

no

in conclusion

In summary, to find out if you can use a subsequence of steps in the string S to get the circumference of a circle centered at the origin, you can use any of the above methods. The second method is a faster method but uses extra space, while the first method is a brute force method that is not very efficient but easy to understand.

The above is the detailed content of Checks whether it is possible to reach any point on the circumference of a given circle from the origin. For more information, please follow other related articles on the PHP Chinese website!