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:

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)

Solution

class Solution {
public:
    struct point {
        int x, y;
        point(int x0, int y0): x(x0), y(y0) {};
    };

    bool isCrossing(vector<point*> points, int a, int b, int c, int d){
        if ( a < 0 or b < 0 or c < 0 or d < 0 ) return false;
        point *l10 = points[a], *l11 = points[b], *l20 = points[c], *l21 = points[d];
        int x10 = l10->x, y10 = l10->y, x11 = l11->x, y11 = l11->y;
        int x20 = l20->x, y20 = l20->y, x21 = l21->x, y21 = l21->y;
        if ( x10 == x11 ) {
            return ( (x10-x20)*(x10-x21) <= 0 and ( (y20-y11)*(y20-y10) <= 0 or (y21-y11)*(y21-y10) <= 0 ) );
        }
        if ( y10 == y11 ) {
            return ( (y10-y20)*(y10-y21) <= 0 and ( (x20-x11)*(x20-x10) <= 0 or (x21-x11)*(x21-x10) <= 0 ) );
        }
        return false;
    }
    bool isSelfCrossing(vector<int>& x) {
        int n = x.size();
        if ( n <= 3 ) false;
        vector<point*> points;
        points.push_back(new point(0, 0));
        vector<pair<int, int>> e;
        e.push_back(pair<int, int>(0, 1));
        e.push_back(pair<int, int>(-1, 0));
        e.push_back(pair<int, int>(0, -1));
        e.push_back(pair<int, int>(1, 0));
        int x0 = 0, y0 = 0, np;
        for ( int i = 0; i < n; i++ ) {
            x0 += e[i%4].first * x[i];
            y0 += e[i%4].second * x[i];
            points.push_back(new point(x0, y0));
            if ( int(points.size()) == 8 ) points.erase(points.begin());
            np = points.size();
            if ( isCrossing(points, np-1, np-2, np-4, np-5) ) return true;
            if ( isCrossing(points, np-1, np-2, np-5, np-6) ) return true;
            if ( isCrossing(points, np-1, np-2, np-6, np-7) ) return true;
        }
        return false;
    }
};

Notes
关键是提取出“可能相交”的三种情况，除了题干中给的example1和example3， 还可能有以下这种情况：

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

这三种情况分别对应：

• 第i条线段和第(i-3)条线段相交；
• 第i条线段和第(i-4)条线段相交；
• 第i条线段和第(i-5)条线段相交。 只需要对这三组线段的相交情况进行判断即可。