题解 | #交叉线#

假设两个半圆的坐标分别是 (x1,x2), (y1, y2)，其中 x2>x1 && y2>y1,那么两个圆是否相交的条件可以有：

• y2 > x2 > y1 > x1
• x2 > y2 > x1 > y1

这两种情况对应下面的 isInterSectA 和 isInterSectB，这个题的空间复杂度只需要 O(1) 即上述的 4 个点即可，为了减少代码量，这里使用了数组，可以优化一下。

需要循环判断所有点，所以时间复杂度是 O(N)。

flag = flag || isInterSectA(dotVec, dotVec.size()-1) || isInterSectB(dotVec, dotVec.size()-1); 这句话将 flag 判断放到最前面，一旦出现符合的情况，之后就不再判断情况1和情况 2，稍微优化了一下。

#include <bits/stdc++.h>
using namespace std;

bool isInterSectB(vector<int> &dotVec, int i) {
    return max(dotVec[i-2], dotVec[i-3]) > max(dotVec[i], dotVec[i-1])  && 
        max(dotVec[i], dotVec[i-1]) > min(dotVec[i-2], dotVec[i-3]) && 
        min(dotVec[i-3], dotVec[i-2]) > min(dotVec[i], dotVec[i-1]);
}

bool isInterSectA(vector<int> &dotVec, int i) {
    return max(dotVec[i], dotVec[i-1]) > max(dotVec[i-2], dotVec[i-3]) && 
        max(dotVec[i-2], dotVec[i-3]) > min(dotVec[i], dotVec[i-1]) && 
        min(dotVec[i], dotVec[i-1]) > min(dotVec[i-3], dotVec[i-2]);
}


int main() {
    int sample, dotNum, dot; cin >> sample;
    while (sample--) {
        cin >> dotNum;
        vector<int> dotVec; bool flag = false;
        while (dotNum--) {
            cin >> dot;
            if (dotVec.size() < 4) {
                dotVec.push_back(dot);
            } 
            if (dotVec.size() >= 4) {
                flag = flag || isInterSectA(dotVec, dotVec.size()-1) || isInterSectB(dotVec, dotVec.size()-1);
                dotVec.push_back(dot);
            } 
        }
        cout << (flag ? "y" : "n") << endl;
    }
    return 0;
}