关注
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
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
10-23 15:58
华中农业大学 Java
LZStarV:冲就好了,就算真的是字节也冲,面评脏了大不了等三四个月就淡了,而且等到那个时候实力进步了选择还多,何必拘泥于字节 点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 你的秋招白月光和意难平公司 #
27388次浏览 225人参与
# 机械制造面试点评 #
77694次浏览 463人参与
# 你想跟着什么样领导? #
19049次浏览 166人参与
# 扒一扒那些奇葩实习经历 #
134665次浏览 1130人参与
# 十一月总结 #
32644次浏览 294人参与
# 实习吐槽大会 #
393477次浏览 2163人参与
# 机械/制造每日一题 #
77327次浏览 1390人参与
# 职场上哪些事情令人讨厌 #
29471次浏览 120人参与
# 机械人晒出你的简历 #
141362次浏览 865人参与
# 毕业季,你想好怎么跟生活对线了吗? #
258914次浏览 3845人参与
# 分享一个让你热爱工作的瞬间 #
50750次浏览 441人参与
# 运营人的第一份offer应该如何选 #
198421次浏览 1225人参与
# 入职以后才知道的校招谎言 #
107183次浏览 668人参与
# 硬件人秋招进展 #
253186次浏览 3942人参与
# 如何提高实习转正率? #
59873次浏览 420人参与
# 什么样的背景能拿SSP? #
122076次浏览 422人参与
# 深信服求职进展汇总 #
239687次浏览 1803人参与
# 机械人还在等华为开奖吗? #
284767次浏览 1447人参与
# 国央企笔面经互助 #
169611次浏览 1207人参与
# 从夯到拉,评价编程语言 #
14874次浏览 111人参与