C 0ms O(n) time and O(1) space soln


  • 0
    1
    struct line{
      int x1;
      int x2;
      int y1;
      int y2;
    };
    
    #define CROSSING 1
    #define NO_CROSSING 0
    enum directions { NORTH=0, WEST, SOUTH, EAST, TEMPNS, TEMPEW, MAX};
    
    bool checkCrossing(struct line *lines, int temp) {
      int status = NO_CROSSING;
      switch (temp) {
      case TEMPNS:
        if((lines[temp].x1 == lines[EAST].x1) || (lines[temp].x1 == lines[EAST].x2) ||
           ((lines[temp].x1 < lines[EAST].x2) && (lines[temp].x1 > lines[EAST].x1))) {
          if(((lines[EAST].y1 > lines[temp].y1) && (lines[EAST].y1 < lines[temp].y2)) ||
             ((lines[EAST].y1 > lines[temp].y2) && (lines[EAST].y1 < lines[temp].y1)) ||
             (lines[EAST].y1 == lines[temp].y1) || (lines[EAST].y1 == lines[temp].y2))
            {status = CROSSING ; break;}
        }
        if((lines[temp].x1 == lines[WEST].x1) || (lines[temp].x1 == lines[WEST].x2)||
           ((lines[temp].x1 < lines[WEST].x1) && (lines[temp].x1 > lines[WEST].x2))){ /* NS x1==x2 */
          if(((lines[WEST].y1 > lines[temp].y1) && (lines[WEST].y1 < lines[temp].y2)) ||
             ((lines[WEST].y1 > lines[temp].y2) && (lines[WEST].y1 < lines[temp].y1)) ||
             (lines[WEST].y1 == lines[temp].y1) || (lines[WEST].y1 == lines[temp].y2))
            {status = CROSSING ; break;}
        }
        break;
      case TEMPEW:
        if((lines[temp].y1 == lines[NORTH].y1) || (lines[temp].y1 == lines[NORTH].y2) ||
           ((lines[temp].y1 < lines[NORTH].y2) && (lines[temp].y1 > lines[NORTH].y1)))  {
          if(((lines[NORTH].x1 > lines[temp].x1) && (lines[NORTH].x1 < lines[temp].x2)) ||
             ((lines[NORTH].x1 > lines[temp].x2) && (lines[NORTH].x1 < lines[temp].x1)) ||
             (lines[NORTH].x1 == lines[temp].x1) || (lines[NORTH].x1 == lines[temp].x2))
            {status = CROSSING ; break;}
        }
        if((lines[temp].y1 == lines[SOUTH].y1) || (lines[temp].y1 == lines[SOUTH].y2) ||
           ((lines[temp].y1 < lines[SOUTH].y1) && (lines[temp].y1 > lines[SOUTH].y2)))  {
          if(((lines[SOUTH].x1 > lines[temp].x1) && (lines[WEST].x1 < lines[temp].x2)) ||
             ((lines[SOUTH].x1 > lines[temp].x2) && (lines[WEST].x1 < lines[temp].x1)) ||
             (lines[SOUTH].x1 == lines[temp].x1) || (lines[WEST].x1 == lines[temp].x2))
            {status = CROSSING ; break;}
        }
        break;
      }
    
      return status;
    }
    
    
    bool isSelfCrossing(int* x, int xSize) {
      if(!x) return 0;
      int i, dir=0;
      struct line lines[MAX];
      int curX=0, curY=0;
    
      bzero(lines, sizeof(lines));
    
      for(i=0;i<xSize;i++, dir++)  {
        if(dir >=4) dir =0;
        switch (dir) {
        case NORTH:
          lines[TEMPNS].x1=curX; lines[TEMPNS].x2=curX; lines[TEMPNS].y1=curY; lines[TEMPNS].y2=curY+x[i]; curY+=x[i];
          if((checkCrossing(lines, TEMPNS) == CROSSING) && (i>2)) return CROSSING;
          memcpy(&lines[EAST], &lines[TEMPEW], sizeof(struct line));
          break;
        case WEST:
          lines[TEMPEW].y1=lines[TEMPEW].y2=curY; lines[TEMPEW].x1=curX; lines[TEMPEW].x2=curX-x[i]; curX-=x[i];
          if((checkCrossing(lines, TEMPEW) == CROSSING) && (i>2)) return CROSSING;
          memcpy(&lines[NORTH], &lines[TEMPNS], sizeof(struct line));
          break;
        case SOUTH:
          lines[TEMPNS].x1=lines[TEMPNS].x2=curX; lines[TEMPNS].y1=curY; lines[TEMPNS].y2=curY-x[i]; curY-=x[i];
          if((checkCrossing(lines, TEMPNS) == CROSSING) && (i>2)) return CROSSING;
          memcpy(&lines[WEST], &lines[TEMPEW], sizeof(struct line));
          break;
        case EAST:
          lines[TEMPEW].y1=lines[TEMPEW].y2=curY; lines[TEMPEW].x1=curX; lines[TEMPEW].x2=curX+x[i]; curX+=x[i];
          if((checkCrossing(lines, TEMPEW) == CROSSING) && (i>2)) return CROSSING;
          memcpy(&lines[SOUTH], &lines[TEMPNS], sizeof(struct line));
          break;
        }
      }
      return NO_CROSSING;
    }
    

    Looks complex, but the checkCrossing function just checks if the given line is an intersection between itself and the other direction lines.

    Would love to hear back if there are easier ways to check the intersection than comparing all x's and y's.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.