关注
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
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 你上一次加班是什么时候? #
48386次浏览 336人参与
# 学历or实习经历,哪个更重要 #
92254次浏览 657人参与
# 大疆求职进展汇总 #
476384次浏览 3185人参与
# 秋招想进国企该如何准备 #
49622次浏览 350人参与
# 摸鱼被leader发现了怎么办 #
48238次浏览 322人参与
# 找工作,行业重要还是岗位重要? #
24757次浏览 403人参与
# 生化医药面经大本营 #
99189次浏览 466人参与
# 实习要如何选择和准备? #
51935次浏览 846人参与
# 潍柴工作体验 #
23599次浏览 18人参与
# 你最满意的offer薪资是哪家公司? #
21833次浏览 120人参与
# 如何排解工作中的焦虑 #
148959次浏览 1745人参与
# 来聊聊机械薪资天花板是哪家 #
116170次浏览 721人参与
# 你觉得通信/硬件有必要实习吗? #
98399次浏览 895人参与
# Offer比较,求稳定还是求发展 #
45391次浏览 228人参与
# 金融财会交流会 #
104744次浏览 361人参与
# 硬件兄弟们 甩出你的华为奖状 #
99159次浏览 670人参与
# 24届硬件人与华为的爱恨情仇 #
123775次浏览 962人参与
# 外包能不能当跳板? #
28960次浏览 192人参与
# 机械人与华为的爱恨情仇 #
109247次浏览 923人参与
# 机械人怎么评价今年的华为 #
194235次浏览 1502人参与