python3 ,点5、6有啥特判吗。。。我前面比别人快,但是5,6超时啊
查看原帖
python3 ,点5、6有啥特判吗。。。我前面比别人快,但是5,6超时啊
514478
wuwuwuyingyingying楼主2021/10/6 13:06


class DSU:
    
    def __init__(self , n):
        self.p = [i for i in range(n)]
        self.d = [1 for i in range(n)]
        self.cnt = n
    
    def find(self,i):
        if i != self.p[i]:
            self.p[i] = self.find(self.p[i])
        return self.p[i]
    
    def iscon(self,a,b):
        return self.find(a) == self.find(b)
    
    def union(self,x,y):
        #x = self.find(a)
        #y = self.find(b)
        if x != y:
            if self.d[x] > self.d[y]:
                self.p[y] = x
            elif self.d[x] < self.d[y]:
                self.p[x] = y
            else:
                self.p[y] = x
                self.d[x] += 1
            self.cnt -= 1

def can_conn(r1,r2,b1,b2):
    dis = (b1[0] - b2[0]) * (b1[0] - b2[0]) + (b1[1] - b2[1]) * (b1[1] - b2[1]) + (b1[2] - b2[2]) * (b1[2] - b2[2])
    return dis <= (r1 + r2) * (r1 + r2)

t = int(input())

data = []
for _ in range(t):
    e = []
    one = list(map(int,input().split()))
    e.append(one)
    for _ in range(one[0]):
        e.append(list(map(int,input().split())))
    data.append(e[:])

#print(data)



for d in range(t):
    eve = data[d]
    n,h,r = eve[0]
    d = DSU(n)
    ball = [] #所有的
    up = [] #能到上边界
    down = [] #能到下边界
    flag_all = False
 
    for vv in range(1,n + 1):
        #row = list(map(int,input().split()))
        row = eve[vv]
        #有直接一个洞就满足的?
        if row[2] + r >= h and row[2] - r <= 0:
            flag_all = True
            break
        if row[2] + r >= h:
            up.append(row + [vv-1]) #把下标带进去
        if row[2] - r <= 0:
            down.append(row + [vv-1]) 
        ball.append(row + [vv-1]) 

    if flag_all:
        print("Yes")
    else:
        ball.sort(key = lambda x : x[2]) #按照h排个序
        if ball[0][2] - r > 0 or ball[-1][2] + r < h:
            #如果最低的都不能触底#如果最高的都不能上天
            print("No")
        else:
            #把能连的连了
            for i in range(n):
                for j in range(i + 1,n):
                    #这里加个剪枝,平面坐标上都不能相交的直接不连
                    if 4*r*r < (ball[i][0] - ball[j][0])*(ball[i][0] - ball[j][0]) + (ball[i][1] - ball[j][1])*(ball[i][1] - ball[j][1]):
                        continue
                    if can_conn(r,r,ball[i],ball[j]):
                        a = d.find(ball[i][-1])
                        b = d.find(ball[j][-1])
                        if a != b:
                            d.union(a,b)
                        #if not d.iscon(ball[i][-1],ball[j][-1]):
                            #d.union(ball[i][-1],ball[j][-1]) #连接的是下标
        
            #扫描上下的,看看有没有连接的
            flag = False
            for i in up:
                for j in down:
                    if d.iscon(i[-1],j[-1]):
                        flag = True
                        break
                if flag:
                    break
            if flag:
                print("Yes")
            else:
                print("No")

2021/10/6 13:06
加载中...