交叉线

题解：

考察点： 思维，数形结合，暴力

易错点：

本题中要求的是相交的半圆，如果存在两个半圆，直径分别为和，并且满足，则不属于相交的情况，所以如果按照结束位置排序的方法来贪心并不可行

一定注意题目中明确说明在端点处相交不算相交

解法：

这题通过数形结合的方法更容易理解，设两个半圆的端点分别为和，则相交时有如下图所示的情况：

在有了上述结论后，题目就变得简单，直接对于半圆，直接枚举其前面位置的半圆，看和其是否存在交点，复杂度为

#include "bits/stdc++.h"
using namespace std;
const int maxn=1e3+10;
int T,n;
int a[maxn];
struct node{
    int l,r;
}p[maxn];
int main()
{
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        memset(a,0,sizeof(a));
        memset(p,0,sizeof(p));
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=2;i<=n;i++){
            p[i-1].l=min(a[i-1],a[i]);
            p[i-1].r=max(a[i-1],a[i]);
        }
        --n;
        int flag=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<i;j++){
                if((p[j].l<p[i].r&&p[j].l>p[i].l&&p[j].r>p[i].r)||(p[j].r<p[i].r&&p[j].r>p[i].l&&p[j].l<p[i].l)){
                    flag=1; 
                    break;
                }
            }
            if(flag) break;
        }
        if(!flag) printf("n\n");
        else printf("y\n");
    }
    return 0;
}