首页 > 试题广场 >

交叉线

[编程题]交叉线

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

LitterF

运行时间1806ms，哈哈

加了个2分判断的快一点，不然过90+到不了100

判断的时候固定了右边界升序，固定选一条线段，在其左边找线段，二分的目的是找到左边的右上界满足所有左边的线段右边界！= 固定线段的右边界，因为相等的时候依照题意不算相交。

因为我们已经做升序了，所以左边线段的右边界一定是<=固定线段的，我们需要这个不等条件不满足。

遍历：

左边的左边界 < 右边的左边界 < 左边的右边界 < 右边的右边界的点。可以结束了

只需要判断右边的左边界在(左边的左边界,左边的左边界)里面就行了

T = int(input())
def low_low_bound(data,en,value):
    st = 0
    en-=1
    while st<=en:
        mid = (st+en)//2
        if data[mid][1]<value:
            st = mid + 1
        else:
            en = mid - 1
    return en
for _ in range(T):
    tmp = int(input())
    data = list(map(int,input().split()))
    re = []
    for i in range(len(data)-1):
        re.append((min(data[i],data[i+1]),max(data[i],data[i+1])))
    re.sort(key = lambda x:(x[1],x[0]))
    b = 'n'
    for i in range(1,len(re)):
        if b=='y':
            break
        j_max = low_low_bound(re,i,re[i][1])
               #j_max = i-1
        for j in range(j_max+1):
            if re[i][0]<re[j][1] and re[i][0]>re[j][0]:
                b = 'y'
                break
    print(b)

聪明的你一定想到了，第一次过了90+，肯定是卡的时间边界，那只需要把他改成C++就过了不需要优化哈哈

发表于 2019-10-08 16:47:06 回复(0)

Python

ElonB

""""
找到规律本题不难，对连续的3个值p1，p2，p3
若p3 落在p1、p2中间，则p1、p2区间两侧不能再取值用flag[]=False标记，
否则，p1、p2构成的区间内不能再取值。
by the way：
本题 -1000000 ≤ ai ≤ 1000000，对每一个整数设置并修改flag 时空复杂度较高，
所以通过排序好的b 只对经过的点设置flag，没有经过的点设置flag是没意义的。
"""
if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        n = int(input())
        a = list(map(int, input().strip().split()))
        if len(a) <= 3:
            print('n')
            continue
        b = sorted(a)
        
        flag = [True] * len(b)  # 所有点都可取
        ans = True  # 初始设为没有相交点
        p1, p2 = a[0], a[1]
        for i in range(2, len(a)):
            if flag[b.index(a[i])] == False:  # 判断此点是否在之前标记为不可取
                ans = False  # 存在一个相交点，即停止遍历并输出结果
                break
            if min(p1, p2) < a[i] < max(p1, p2):  # 更新区间外的flag为False
                for j in range(0, b.index(min(p1, p2))):
                    flag[j] = False
                for j in range(b.index(max(p1, p2)) + 1, len(b)):
                    flag[j] = False
            else:  # 更新区间内flag为False
                for j in range(b.index(min(p1, p2)) + 1, b.index((max(p1, p2)))):
                    flag[j] = False
            p1, p2 = p2, a[i]
        print('n' if ans else 'y')

发表于 2019-07-16 16:21:48 回复(0)