此题的解法非常精妙。
试想一下,如果这样的操作能够无限进行下去而不相交,那必然是一个螺旋膨胀的图形,需要满足什么条件呢?很简单,只要永远比对面的那个线段更长即可
while (x[i]>x[i-2])
i++;
一旦这种趋势无法保持,但仍想要不self-crossing的话,那么之后必然形成的是一个螺旋收缩的图形了(因为永远是逆时针地行进)。条件也很简单,只要永远比对面的那个线段更短即可:
while (x[i]<x[i-2])
i++;
当然这种螺旋收缩的趋势不会是无限的。
但是,对于从膨胀到收缩的临界线段x[i],我们需要有一个额外的判断:
if (x[i]>x[i-2]-x[i-4])
x[i-1]-=x[i-3];
i++;
以上这步操作其实框定了螺旋收缩的范围。需要仔细体会。