My Java solution. Straight forward

• The intersect happens only in 2 cases.

case 1: if go up, it may intersect the last top or the second last bottom. the same goes for go left and go down and go right.You have to keep track the last 8 segments.

case 2: this is tricky. It only happens in the fifth step. Going up and go through the (0,0).

``````public class Solution {
public boolean isSelfCrossing(int[] x) {
// older
int[] top0 = null;
int[] left0 = null;
int[] bottom0 = null;
int[] right0 = null;
// neweast
int[] top1 = null;
int[] left1 = null;
int[] bottom1 = null;
int[] right1 = null;

int[] cur = new int[4];
for(int i=0;i<x.length;i++) {
int[] tmp = new int[4];
int v = x[i];
switch(i%4){
case 0:
setVec(tmp,cur,0,v);
if(top1 != null && isIntersect(top1,tmp) || bottom0 != null && isIntersect(bottom0,tmp)
// sepecial case: line go though (0,0)
|| tmp[0] == 0 && tmp[1] <0 && tmp[2] == 0 && tmp[3] >= 0) {
return true;
}
cur = tmp;
right0 = right1;
right1 = cur;
break;
case 1:
setVec(tmp,cur,-v,0);
if(left1 != null && isIntersect(left1,tmp) || right0 != null && isIntersect(right0,tmp)) {
return true;
}
cur = tmp;
top0 = top1;
top1 = cur;
break;
case 2:
setVec(tmp,cur,0,-v);
if(bottom1 != null && isIntersect(bottom1,tmp) || top0 != null && isIntersect(top0,tmp)) {
return true;
}
cur = tmp;
left0 = left1;
left1 = cur;
break;
case 3:
setVec(tmp,cur,v,0);
if(right1 != null && isIntersect(right1,tmp) || left0 != null && isIntersect(left0,tmp) ) {
return true;
}
cur = tmp;
bottom0 = bottom1;
bottom1 = cur;
break;
}
}
return false;
}
private void setVec(int[] dest, int[] source,int x,int y) {
dest[0] = source[2];
dest[1] = source[3];
dest[2] = source[2] + x;
dest[3] = source[3] + y;
}
private boolean isIntersect(int[] a,int[] b) {

if(a[0] == a[2]) {
return b[1] >= Math.min(a[1],a[3]) && b[1] <= Math.max(a[1],a[3]) &&
a[0] >= Math.min(b[0],b[2]) && a[0] <= Math.max(b[0],b[2]);
}
return isIntersect(b,a);
}
}``````

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