Question

Formatted question description: https://leetcode.ca/all/335.html

 335 Self Crossing

 You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north,
 then x[1] metres to the west, x[2] metres to the south, x[3] metres to the east and so on.

 In other words, after each move your direction changes counter-clockwise.

 Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.



 Example 1:

 ┌───┐
 │   │
 └───┼──>
 │

 Input: [2,1,1,2]
 Output: true


 Example 2:

 ┌──────┐
 │      │
 │
 │
 └────────────>

 Input: [1,2,3,4]
 Output: false


 Example 3:

 ┌───┐
 │   │
 └───┼>

 Input: [1,1,1,1]
 Output: true

Algorithm

In fact, there are only three cases of intersection:

     x(1)
    ┌───┐
x(2)│   │x(0)
    └───┼──>
    x(3)│

The first type is the case where the fourth side and the first side intersect. The conditions that need to be met are that the first side is greater than or equal to the third side, and the fourth side is greater than or equal to the second side. The same applies to the case where the fifth side intersects the second side, the sixth side intersects the third side, and so on, and so on.

x(1)
    ┌──────┐
    │      │x(0)
x(2)│      ^
    │      │x(4)
    └──────│
      x(3)

The second type is the case where the fifth side and the first side overlap and intersect. The conditions that need to be met are that the second side and the fourth side are equal, and the fifth side is greater than or equal to the third side and the first side. The difference is also applicable to the case where the sixth edge and the second edge overlap and intersect, and so on, and so on…

x(1)
    ┌──────┐
    │      │x(0)
x(2)│     <│────│
    │       x(5)│x(4)
    └───────────│
        x(3)

The third category is the intersection of the sixth side and the first side. The conditions that need to be met are that the fourth side is greater than or equal to the second side, the third side is greater than or equal to the fifth side, and the fifth side is greater than or equal to The difference between the third side and the first side, the sixth side is greater than or equal to the difference between the fourth side and the second side, the same applies to the intersection of the seventh side and the second side, and so on.

Code

Java

public class Self_Crossing {

    class Solution {
        public boolean isSelfCrossing(int[] x) {
            for (int i = 3; i < x.length; ++i) {
                if (x[i] >= x[i - 2] && x[i - 3] >= x[i - 1]) {
                    return true;
                }
                if (i >= 4 && x[i-1] == x[i-3] && x[i] >= x[i-2] - x[i-4]) {
                    return true;
                }
                if (i >= 5 && x[i-2] >= x[i-4] && x[i-3] >= x[i-1] && x[i-1] >= x[i-3] - x[i-5] && x[i] >= x[i-2] - x[i-4]) {
                    return true;
                }
            }
            return false;
        }
    }

}

```
Todo
```

class Solution(object):
  def isSelfCrossing(self, x):
    """
    :type x: List[int]
    :rtype: bool
    """
    if len(x) < 4:
      return False
    for i in range(3, len(x)):
      if x[i] >= x[i - 2] and x[i - 1] <= x[i - 3]:
        return True
      if i >= 4 and x[i - 1] == x[i - 3] and x[i] + x[i - 4] >= x[i - 2]:
        return True
      if i >= 5 and x[i - 1] <= x[i - 3] and x[i - 3] <= x[i - 1] + x[i - 5] and x[i] + x[i - 4] >= x[i - 2] and x[
        i - 4] <= x[i - 2]:
        return True
    return False

335 - Self Crossing

Question

Algorithm

Code

All Problems

All Solutions