首页 > 试题广场 > 交叉线
[编程题]交叉线
M布置给小M一个题目:首先给出n个在横坐标上的点,然后连续的用半圆连接他们:首先连接第一个点与第二点(以第一个点和第二点作为半圆的直径)。然后连接第二个第三个点,直到第n个点。现在需要判定这些半圆是否相交了,在端点处相交不算半圆相交。如下图所示。


输入描述:
输入的第一行包含一个整数T (1 ≤ T ≤ 10)表示有T组样例。

每组样例的第一行是一个整数n (1≤n≤1000)。

接下来的一行输入有n个用空格隔开的不同的整数a1,a2,...,an (-1000000 ≤ ai ≤ 1000000),(ai,0)表示第i个点在横坐标的位置。


输出描述:
对于每个输入文件,输出T行。

每行输出"y"表示这些半圆有相交或者"n"。
示例1

输入

2
4
0 10 5 15
4
0 15 5 10

输出

y
n

2个回答

添加回答
递归层数太多,通不过,迭代不太好写吧!
#include<vector>
#include<iostream>
using namespace std;
void func1(vector<int> v,int n,int j,int mini,int mid,int maxi);
void func2(vector<int> v,int n,int j,int mini,int mid,int maxi);
void func3(vector<int> v,int n,int j,int mini,int mid,int maxi);
bool flag=true;
void func1(vector<int> v,int n,int j,int mini,int mid,int maxi){
    //下一个可以<min,可以>max,可以大于mid小于max
    for(int i=j;i<n;i++){
        if(v[i]>maxi) func1(v,n,i+1,mini,maxi,v[i]);
        else if(v[i]<mini) func2(v,n,i+1,v[i],mini,maxi);
        else if(v[i]>mid && v[i]<maxi) func3(v,n,i+1,mid,v[i],maxi);
        else{
            flag=false;
            return;
        }
    }
}
void func2(vector<int> v,int n,int j,int mini,int mid,int maxi){
    //下一个可以<min,可以>max,可以大于min小于mid
    for(int i=j;i<n;i++){
        if(v[i]>maxi) func2(v,n,i+1,mini,maxi,v[i]);
        else if(v[i]<mini) func1(v,n,i+1,v[i],mini,maxi);
        else if(v[i]>mini && v[i]<mid) func3(v,n,i+1,mini,v[i],mid);
        else{
            flag=false;
            return;
        }
    }
}

void func3(vector<int> v,int n,int j,int mini,int mid,int maxi){
    //下一个可以大于min小于mid,可以大于mid小于max
    for(int i=j;i<n;i++){
        if(v[i]>mini && v[i]<mid) func3(v,n,i+1,mini,v[i],mid);
        else if(v[i]>mid && v[i]<maxi) func3(v,n,i+1,mid,v[i],maxi);
        else{
            flag=false;
            return;
        }
    }
}

int main(){
    int t,n;
    cin>>t;
    for(int i=0;i<t;i++){
        cin>>n;
        vector<int> v(n);
        for(int j=0;j<n;j++){
            cin>>v[j];
        }
        if(n<=2){
            cout<<"y"<<endl;
            continue;
        }
        flag=true;
        if(v[0]<v[1]) {
            func1(v,n,2,v[0],v[0],v[1]);
        }
        else{
            func2(v,n,2,v[1],v[1],v[0]);
        }
        if(flag) cout<<"y"<<endl;
        else cout<<"n"<<endl;

    }

    return 0;
}


发表于 2019-04-20 11:23:51 回复(0)
我已经尽量简化计算了,但只要有两层循环就超时😓
if __name__=='__main__':
    try:
        T=int(input().strip())
        for i in range(T):
            n=int(input().strip())
            if n<=3:
                print('n')
            else:
                l=list(map(int,input().strip().split()))
                tag = 'n'
                for j in range(n-3):
                    k=j+2
                    while k+1<n:
                        min1=min(l[j],l[j+1])
                        max1=max(l[j],l[j+1])
                        min2 = min(l[k], l[k + 1])
                        max2 = max(l[k], l[k + 1])
                        if (min1>min2 and max1<max2) or (min1<min2 and max1>max2) or(min1>max2) or (min2>max1):
                            k=k+1
                        else:
                            tag='y'
                            break
                    if tag=='y':
                        break
                print(tag)
    except:
        pass
修改后是这样,可以通过,但枚举条件好像有点傻😂
if __name__=='__main__':
    try:
        T = int(input().strip())
        for i in range(T):
            n = int(input().strip())
            if n <= 3:
                print('n')
            else:
                l = list(map(int, input().strip().split()))
                l1 = []
                for j in range(n):
                    l1.append((j, l[j]))
                l1=sorted(l1, key=lambda s: s[1])
                tag = 'n'
                for k in range(n - 1):
                    a = l1.index((l1[k][0], l[l1[k][0]]))
                    b = l1.index((l1[k+1][0], l[l1[k+1][0]]))
                    al = l1.index((l1[k][0] - 1,l[l1[k][0] - 1])) if l1[k][0] > 0 else None
                    ar = l1.index((l1[k][0] + 1,l[l1[k][0] + 1])) if l1[k][0] < n - 1 else None
                    bl = l1.index((l1[k + 1][0] - 1,l[l1[k + 1][0] - 1])) if l1[k + 1][0] > 0 else None
                    br = l1.index((l1[k + 1][0] + 1,l[l1[k + 1][0] + 1])) if l1[k + 1][0] < n - 1 else None
                    if al and bl and ((al < b and b < a) and (bl > a or bl < al)):
                        tag = 'y'
                        break
                    if al and bl and ((al < bl and bl < a) and (b > a or b < al)):
                        tag = 'y'
                        break
                    if al and br and ((al < b and b < a) and (br > a or br < al)):
                        tag = 'y'
                        break
                    if al and br and ((al < br and br < a) and (b > a or b < al)):
                        tag = 'y'
                        break
                    if ar and bl and ((ar < b and b < a) and (bl > a or bl < ar)):
                        tag = 'y'
                        break
                    if ar and bl and ((ar < bl and bl < a) and (b > a or b < ar)):
                        tag = 'y'
                        break
                    if ar and br and ((ar < b and b < a) and (br > a or br < ar)):
                        tag = 'y'
                        break
                    if ar and br and ((ar < br and br < a) and (b > a or b < ar)):
                        tag = 'y'
                        break
                    if al and bl and ((b < al and al < bl) and (a > bl or a < b)):
                        tag = 'y'
                        break
                    if al and bl and ((b < a and a < bl) and (al > bl or al < b)):
                        tag = 'y'
                        break
                    if ar and bl and ((b < ar and ar < bl) and (a > bl or a < b)):
                        tag = 'y'
                        break
                    if ar and bl and ((b < a and a < bl) and (ar > bl or ar < b)):
                        tag = 'y'
                        break
                    if al and br and ((b < al and al < br) and (a > br or a < b)):
                        tag = 'y'
                        break
                    if al and br and ((b < a and a < br) and (al > br or al < b)):
                        tag = 'y'
                        break
                    if ar and br and ((b < ar and ar < br) and (a > br or a < b)):
                        tag = 'y'
                        break
                    if ar and br and ((b < a and a < br) and (ar > br or ar < b)):
                        tag = 'y'
                        break
                print(tag)
    except:
        pass

发表于 2019-04-16 10:07:12 回复(0)

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

扫描二维码,关注牛客网公众号