<p>You are given an array of integers <code>distance</code>.</p>

<p>You start at the point <code>(0, 0)</code> on an <strong>X-Y plane,</strong> and you move <code>distance[0]</code> meters to the north, then <code>distance[1]</code> meters to the west, <code>distance[2]</code> meters to the south, <code>distance[3]</code> meters to the east, and so on. In other words, after each move, your direction changes counter-clockwise.</p>

<p>Return <code>true</code> <em>if your path crosses itself or </em><code>false</code><em> if it does not</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/12/21/11.jpg" style="width: 400px; height: 413px;" />
<pre>
<strong>Input:</strong> distance = [2,1,1,2]
<strong>Output:</strong> true
<strong>Explanation:</strong> The path crosses itself at the point (0, 1).
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/12/21/22.jpg" style="width: 400px; height: 413px;" />
<pre>
<strong>Input:</strong> distance = [1,2,3,4]
<strong>Output:</strong> false
<strong>Explanation:</strong> The path does not cross itself at any point.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/12/21/33.jpg" style="width: 400px; height: 413px;" />
<pre>
<strong>Input:</strong> distance = [1,1,1,2,1]
<strong>Output:</strong> true
<strong>Explanation:</strong> The path crosses itself at the point (0, 0).
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;=&nbsp;distance.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;=&nbsp;distance[i] &lt;= 10<sup>5</sup></code></li>
</ul>

static const int iofast = [](){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  return 0;
}();

struct vec  {
  int x = {};
  int y = {};
};

struct line {
  vec u = {};
  vec v = {};
};

line q[100000+1];
int l = {};
int r = {};

class Solution {
public:
  bool isSelfCrossing(vector<int>& a) {
    auto intersection = [](line l1, line l2){
      return ((l1.u.x >= l2.v.x && l2.u.x >= l1.v.x) || (l1.v.x >= l2.u.x && l2.u.x >= l1.v.x) || (l1.u.x >= l2.v.x && l2.v.x >= l1.u.x) || (l1.v.x >= l2.u.x && l2.v.x >= l1.u.x)) && ((l1.u.y >= l2.v.y && l2.u.y >= l1.v.y) || (l1.v.y >= l2.u.y && l2.u.y >= l1.v.y)  || (l1.u.y >= l2.v.y && l2.v.y >= l1.u.y) || (l1.v.y >= l2.u.y && l2.v.y >= l1.u.y));
    };
    l = r = 0;
    vector<line> lines = {};
    int next_dir[] = {1,2,3,0};
    int dir = {};
    vec p = {0, 0};
    for (auto d : a) {
      vec t = {};
      switch (dir) {
      case 0: t = vec{p.x, p.y+d}; break;
      case 1: t = vec{p.x-d, p.y}; break;
      case 2: t = vec{p.x, p.y-d}; break;
      case 3: t = vec{p.x+d, p.y}; break;
      }
      line curr = {p, t};
      // cout << "(" << p.x << "," << p.y << ") (" << t.x << "," << t.y << ")" << endl;
      p = t;
      for (int i = l; i < r-1; i++) {
        if (intersection(curr, q[i])) {
          return true;
        }
      }
      dir = next_dir[dir];
      q[r++] = curr;
      if (r-l > 6) {
        l++;
      }
    }
    return false;
  }
};
22600