首页 > 试题广场 >

交叉线

[编程题]交叉线

热度指数：5065 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

大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

输入

输出

y
n

算法知识视频讲解

Java

牛客196305255号

import java.util.*;
public class Main{
    private static final int COUNT=6;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int t=sc.nextInt();
            for(int i=0;i<t;i++){
                boolean bool=true;
                int n=sc.nextInt();
                TreeSet<Integer> set=new TreeSet<>();
                int a=sc.nextInt();
                set.add(a);
                for(int j=1;j<n;j++){
                    int b=sc.nextInt();
                    set.add(b);
                    int max=Math.max(a,b);
                    int min=Math.min(a,b);
                    if(bool&&(max!=set.higher(min))&&!(min==set.first()&&max==set.last())){
                        bool=false;
                    }
                    a=b;
                }
                if(bool)
                    System.out.println("n");
                else
                   System.out.println("y"); 
            }
        }
        sc.close();
    }
}

发表于 2021-03-25 14:58:15 回复(0)