题解 | #交叉线# 数学

不用排序，直接拿每个圆全部判断一次，找到就跳出即可。

判断圆是否相交，其实不用想的太复杂，只需要两个圆的坐标两两对比即可：

用pair数对的first和second分别表示圆的左右端点，

那么用甲圆的first、second分别与乙圆的first、second交叉对比，就有三个条件联立判断：

甲的first与乙的first、甲的first与乙的second、甲的second与乙的second，

但需注意由于并未对圆进行排序，因此无法界定甲圆和乙圆谁在数轴上更靠后，因此需分别讨论，最后取“或”

#include <any>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int T;
    while (cin >> T) {
        int n;
        while (cin >> n) {
            vector<int> points;
            int p;
            for (int i = 0; i < n; i++) {
                cin >> p;
                points.push_back(p);
            }
            int x, y;
            vector<pair<int, int>> circles;
            for (int i = 0; i < n - 1; i++) {
                circles.emplace_back(points[i], points[i + 1]);
            }
            // 为了方便后面的计算，确保每个半圆是左端点的值小于右端点的值，也可以在添加时判断
            for (auto& circle : circles) {
                if (circle.first > circle.second) {
                    swap(circle.first, circle.second);
                }
            }
            // 标志是否找到交叉
            bool flag = false;
            for (int i = 0; i < circles.size(); i++) {
                for (int j = i + 1; j < circles.size(); j++) {
                    if ((circles[i].second > circles[j].first &&
                            circles[i].second < circles[j].second &&
                            circles[i].first < circles[j].first) ||
                            (circles[i].first < circles[j].second &&
                             circles[i].second > circles[j].second &&
                             circles[i].first > circles[j].first)) {
                        flag = true;
                        break;
                    }
                }
                if (flag) {
                    break;
                }
            }
            cout << (flag ? 'y' : 'n') << endl;
        }
    }
    return 0;
}

时间复杂度：O(n^2)，用于双重循环判断相交

空间复杂度：O(n)，用于存储圆的左右端点