10
#yyds干货盘点# 解决名企真题：交叉线
source link: https://blog.51cto.com/u_15488507/5449432
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 解决名企真题：交叉线
原创1.简述：
描述
大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
4
0 10 5 15
4
0 15 5 10
2.代码实现：
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");
}
}
}
}
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");
}
}
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK