当前位置：网站首页>＃yyds干货盘点＃解决名企真题：交叉线

＃yyds干货盘点＃解决名企真题：交叉线

2022-07-07 12:42:00 【51CTO】

1.简述：

描述

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

#yyds干货盘点# 解决名企真题：交叉线_java

输入描述：

输入的第一行包含一个整数T (1 ≤ T ≤ 10)表示有T组样例。每组样例的第一行是一个整数n (1≤n≤1000)。接下来的一行输入有n个用空格隔开的不同的整数a1,a2,...,an (-1000000 ≤ ai ≤ 1000000)，(ai,0)表示第i个点在横坐标的位置。

输出描述：

对于每个输入文件，输出T行。每行输出"y"表示这些半圆有相交或者"n"。

示例1

输入：

输出：

2.代码实现：

1.

       
       import java.util.*;
       
public class Main{
       
    public static void main(String[] args) {
       
        Scanner in = new Scanner(System.in);
       
        int T = in.nextInt();
       
        while (T-- > 0){
       
            int n = in.nextInt();//端点数
       
            int[] arr = new int[n];
       
            for (int i = 0; i < n; i++) {//输入端点
       
                arr[i] = in.nextInt();
       
            }
       
            List<int[]> cir = new ArrayList<>();
       
            for (int i = 0; i < n - 1; i++) {//储存圆
       
                int left = Math.min(arr[i],arr[i + 1]);//左端点
       
                int right = Math.max(arr[i],arr[i + 1]);//右端点
       
                cir.add(new int[]{left,right});
       
            }
       
            //题意为所有的圆都不存在相交，才返回false
       
            boolean flag = false;
       
            for (int i = 1; i < cir.size(); i++) {
       
                for (int j = 0; j < i; j++) {
       
                    //先设置两个圆的端点
       
                    int left1 = cir.get(i)[0],right1 = cir.get(i)[1];//圆1的端点
       
                    int left2 = cir.get(j)[0],right2 = cir.get(j)[1];//圆2的端点
       
                    //两圆相交的情况
       
                    if (left1 < left2 && right1 < right2 && right1 > left2){
       
                        flag = true;
       
                        break;
       
                    }else if (left1 > left2 && left1 < right2 && right1 > right2){
       
                        flag = true;
       
                        break;
       
                    }
       
                }
       
            }
       
            if (flag){
       
                System.out.println("y");
       
            }else {
       
                System.out.println("n");
       
            }
       
        }
       
    }
       
}
       
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.