首页 > 试题广场 >

交叉线

[编程题]交叉线

热度指数：5225 时间限制：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

算法知识视频讲解

Python 3

牛客427113308号

count1=int(input())
list1=[]
list2=[]
for i in range(count1):
list1.append(int(input()))
list2.append(list(map(int,input().split())))
def func1(lst):
lst1=[-1,-1]
lst2=[]
result='n'
for i in range(len(lst)-1):
lst1[0],lst1[1]=lst[i],lst[i+1]
lst1.sort()
lst2.append(tuple(lst1))
for j in range(1,len(lst2)):
for k in range(0,j):
if lst2[j][0]>lst2[k][0] and lst2[j][0]<lst2[k][1]:
if lst2[j][1]>lst2[k][1]:
result='y'
return result
if lst2[j][1]>lst2[k][0] and lst2[j][1]<lst2[k][1]:
if lst2[j][0]<lst2[k][0]:
result='y'
return result
return result
for x in range(len(list2)):
print(func1(list2[x]))

发表于 2022-07-20 22:52:43 回复(0)