# 335 Self Crossing

You are given an array x of n positive numbers. You start at point (0,0) and moves x metres to the north, then x metres to the west, x metres to the south, x 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:
Given x = [2, 1, 1, 2],
┌───┐
│ │
└───┼──>
Return true (self crossing)
Example 2:
Given x = [1, 2, 3, 4],
┌──────┐
│ │
└────────────>
Return false (not self crossing)
Example 3:
Given x = [1, 1, 1, 1],
┌───┐
│ │
└───┼>
Return true (self crossing)
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;
void print1D(vector<int> &nums) {
for (auto i : nums) cout << i << ' ';
}
/* method:
-
*/
bool isSelfCrossing(vector<int>& x) {
int up, left, down, right = 0;
int nextUp, nextLeft, nextDown, nextRight = 0;
int indexCounter = -1;
while (indexCounter <= x.size()) {
up += x.at(indexCounter++);
left += x.at(indexCounter++);
down += x.at(indexCounter++);
right += x.at(indexCounter++);
if (indexCounter <= x.size()) {
}
nextUp += x.at(indexCounter++);
nextLeft += x.at(indexCounter++);
nextDown += x.at(indexCounter++);
nextRight += x.at(indexCounter++);
// check intersection of two fieldbox's
if (right >= left || nextUp >= down || nextLeft >= left || nextDown >= down) return false;
// test cases passed, update next field box
left = nextLeft;
down = nextDown;
right = nextRight;
up = nextUp;
}
return true;
}
int main()
{
vector<int> test = { 1, 1, 1, 1 };
isSelfCrossing(test);
print1D(test);
}