class point():     def __init__(self,x,y):         self.x = x         self.y = y def isxiangjiao(a,b,c,d):     fc = (c.y-a.y)*(a.x-b.x)-(c.x-a.x)*(a.y-b.y)     fd = (d.y-a.y)*(a.x-b.x)-(d.x-a.x)*(a.y-b.y)     if(fc*fd>0):         return False     return  True import sys  import collections if __name__ == "__main__":     t = int(sys.stdin.readline().strip())     for i in range(t):         n = int(sys.stdin.readline().strip())         roaddict = collections.defaultdict(set)         roadpos = []         count = 1         for j in range(n):             line = sys.stdin.readline().strip().split()             if(line[0]=='T'):                 x1,y1,x2,y2 = int(line[1]),int(line[2]),int(line[3]),int(line[4])                 pointa = point(x1,y1)                 pointb = point(x2,y2)                 roadpos.append([pointa,pointb])                 if(count==1):                     roaddict[count].add(count)                     count+=1                 else:                     visited = set()                     for tmpi in range(1,len(roadpos)+1):                         pointc = roadpos[tmpi-1][0]                         pointd = roadpos[tmpi-1][1]                         if(tmpi not in visited and isxiangjiao(pointa, pointb, pointc, pointd)):                             visited.add(tmpi)                             roaddict[tmpi].add(count)                             roaddict[count].add(count)                             for tmp in roaddict[tmpi]:                                 visited.add(tmp)                                 roaddict[tmp].add(count)                                 roaddict[count].add(tmp)                     for tmp in roaddict[count]:                         roaddict[tmp] = roaddict[count]                     count+=1             if(line[0]=='Q'): #                 print(roaddict)                 queryvale = int(line[1])                 print(len(roaddict[queryvale]))         print()
点赞 1

相关推荐

04-11 21:31
四川大学 Java
野猪不是猪🐗:(ja)va学弟这招太狠了
点赞 评论 收藏
分享
牛客网
牛客企业服务