Vérifier S'il existe un Cercle

Vous devez exécuter 1 itération pour calculer la nouvelle position, dire newx, newy.
Ensuite, vous calculez les 4 plus d'itérations pour voir si le robot est de retour à newx-newy. Si oui, alors le cercle existe, d'autre pas.

Le rayon de la distance maximale que le robot s'aventura dans son itération.

Mise en œuvre du Code -

//North, South, East, West directions
#define N 0 
#define S 1
#define E 2
#define W 3

//Function to compute the new pos (x, y, dir) after completing one iteration of the string.
//It will also update the max radius.
void findNewPos(char *str, int *origdir, int *origx, int *origy, double *maxrad) {
  int i, len, x, y, dir; 

  dir = *origdir;
  x = *origx;
  y = *origy;

  len = strlen(str);
  i=0;

  //Iterate through each character
  while(i < len) {
    char c = str[i];

    switch(c) {
    case 'L': //Turn left
      switch(dir) {
      case N:
         x--;
         dir = W;
         break;
      case S:
         x++;
         dir = E;
         break;
      case E:
         y++;
         dir = N;
         break;
      case W:
         y--;
         dir = S;
         break;
      }
      break;

    case 'R': //Turn right
      switch(dir) {
      case N:
         x++;
         dir = E;
         break;
      case S:
         x--;
         dir = W;
         break;
      case E:
         y--;
         dir = S;
         break;
      case W:
         y++;
         dir = N;
         break;
      }
      break;

    case 'F': //Go forward
      switch(dir) {
      case N:
         y++;
         dir = N;
         break;
      case S:
         y--;
         dir = S;
         break;
      case E:
         x++;
         dir = E;
         break;
      case W:
         x--;
         dir = W;
         break;
      }
      break;
    }

    //Update max radius till now
    double rad = x*x + y*y;
    if(rad > *maxrad)
      *maxrad = rad;
    i++;
  }

  *origx = x;
  *origy = y;
  *origdir = dir;
}

//Function to compute the max radius of movement, if bounded
double findCircle(char *str) {
  int x=0, y=0, dir=N;
  int refx, refy;
  double radius = 0, maxrad = 0;

  //Starting from origin(x=0, y=0), find new pos after single iteration
  findNewPos(str, &dir, &x, &y, &maxrad);

  refx = x;
  refy = y;

  //Find new positions after 4 more iterations
  findNewPos(str, &dir, &x, &y, &maxrad);
  findNewPos(str, &dir, &x, &y, &maxrad);
  findNewPos(str, &dir, &x, &y, &maxrad);
  findNewPos(str, &dir, &x, &y, &maxrad);

  //Are we back to position where we were after 1st iteration?
  if(x == refx && y == refy) {
    printf("Circle exists %f!\n", maxrad);
    radius = sqrt(maxrad);
  }
  else {
    printf("Circle does not exist!\n");
    radius = -1;
  }

  return radius;
}

string doesCircleExists(string commands) {
    int dir=1; //1 is east; 2 north etc.
    pair<int,int> pos; 
    pos = make_pair(0,0);  //start at origin
    for(int i=0;i<4;i++) {
    for(int i=0;i<commands.size(); i++)
    {
       if(commands[i]=='F')
       {
        if(dir==1) pos.first++;  if(dir==2) pos.second++; 
        if(dir==3) pos.first--; if(dir==0) pos.second--; 
       }
       if(commands[i]=='L') {dir++; dir = dir%4;}
       if(commands[i]=='R') {dir--; dir = dir%4;}
    }
    }
    if(pos.first==0 && pos.second==0 && dir=1) return "YES"; else return "NO";

}

#include <bits/stdc++.h>
using namespace std;
struct point
{
    int x;
    int y;
    int dir;
};
int mod4(int a)
{
    if(a%4 < 0)
        return (a%4 + 4);
    else
        return a%4;
}
int main()
{
    struct point p;
    p.x = 0;
    p.y = 0;
    p.dir = 0;
    string s;cin>>s;
    int j;
    for(int i=0;i<4*s.size();i++)
    {
        j = i%s.size();
        if(s[j] == 'F')
        {
            if(p.dir == 0)//north
                p.y++;
            if(p.dir == 1)//east
                p.x++;
            if(p.dir == 2)//south
                p.y--;
            if(p.dir == 3)//west
                p.x--;
        }
        if(s[j] == 'L')
        {
            p.dir--;
            p.dir = mod4(p.dir);
        }
        if(s[j] == 'R')
        {
            p.dir++;
            p.dir = mod4(p.dir);
        }
        //cout<<p.x<<" "<<p.y<<" "<<p.dir<<endl;
    }
    if(p.x == 0 && p.y ==0 && p.dir == 0)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;   
}

Parcourir la chaîne donnée en une fois et notez le déplacement et la direction dans laquelle vous vous retrouvez. Si le déplacement est non-nul, et le début et la fin directions sont les mêmes pour le robot pour la seule itération, votre robot ne peut pas être contenue dans un cercle, sinon, il peut être.

Figure:

Dans l'illustration, supposons que le robot va d'Un point a à un point B, après une seule itération de la chaîne. Maintenant, l'angle ABC est (90 - thêta), qui fait l'angle ABD égale à 90 degrés. Avec tous les côtés de l'égalité, et à chaque angle égal à 90 degrés, le quadrilatère ABDE est un carré. Cela est vrai pour toute valeur de theta (aigu ou obtus). La preuve serait similaire si la fin de la direction, après une seule itération est à gauche. Pour le sud, le robot va osciller entre les points A et B.

Donc comme une solution à votre problème, vous avez juste à vérifier si le début et la fin de la direction sont les mêmes et que le point de départ et la position d'arrivée ne sont pas les mêmes, après que le robot effectue une itération de la chaîne.