首页 > 试题广场 >

交叉线

[编程题]交叉线

热度指数：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

算法知识视频讲解

Python3

lintoon

def xj(interval_a, interval_b):

start_a, end_a = interval_a

start_b, end_b = interval_b

# 区间相交的条件是：

# 区间A的结束值大于区间B的起始值、A结束值小于B结束值并且区间B的起始值大于区间A的起始值

return start_a < start_b and start_b < end_a and end_b>end_a

T=int(input())

lm=[]

for _ in range(T):

n=int(input())

l=list(map(int,input().split()))

for i in range(n-1):

x=sorted(l[i:i+2])

l[i]=x

l.remove(l[-1])

l.sort(key=lambda x:x[0])

m=False

for j in range(len(l)):

for k in range(j+1,len(l)):

if xj(l[j],l[k]):

print('y')

m=True

break

if m:

break

else:print('n')

发表于 2024-04-11 17:16:20 回复(0)

Python3

琬圭sakura

不知道为什么有部分测试用例会出现ｌｓｉｔ　ｉｎｄｅｘ　ｏｕｔ　ｏｆ　ｒａｎｇｅ的情况

import sys
group=int(input())#获取组数
for f in range(group):
    num=int(input())#获取点数
    points=list(map(int,input().split()))#坐标
    flag=False
    for n in range(num//2):#对于每个圆
        cur_round=[points[2*n],points[2*n+1]]
        # print(cur_round)
        others=points[0:2*n]+points[2*n+2:]
        # print(len(others))
        for i in range(0,len(others),2):#对比每个圆是否只有一个点在其他圆内
            # print(i)
            # print(cur_round[0],others[i],others[i+1])
            # print(cur_round[1],others[i],others[i+1])
            if cur_round[0]>others[i] and cur_round[0]<others[i+1]:
                flag=not flag
                
            if cur_round[1]>others[i] and cur_round[1]<others[i+1]:
                flag=not flag
            if flag:
                print("y")
                break
        if flag:
            break
    if flag:
        continue
    print("n")

发表于 2023-09-15 18:20:26 回复(0)

Python3

牛客926620913号

python3:

最后一组超时啦

while True:
    try:
        n = int(input())
        for case in range(n):
            m1 = int(input())
            list1 = list(map(int,input().split()))
            one = list()
            for i in range(len(list1)):
                if i <m1-1:
                    one.append((list1[i],list1[i+1]))
            count = 0
            flag = False
            #print(one)
            for i in one:
                k1,k2 = i[0],i[1]
                count+=1
                for j in range(count,len(one)):
                    ppp = one[j]
                    p1,p2 = ppp[0],ppp[1]
                    
                    if (min(k1,k2)<min(p1,p2) and max(k1,k2)>min(p1,p2) and max(k1,k2)<max(p1,p2))&nbs***bsp;(max(k1,k2)>max(p1,p2) and min(k1,k2)<max(p1,p2) and min(k1,k2)>min(p1,p2)):
                        flag =True
                        break
                else:
                    continue
                break
            if flag == True:
                print('y')
            else:
                print("n")
                        
        
    except:
        break

发表于 2022-01-08 18:31:48 回复(0)