车道线大师_智加科技笔试题

小林最近打算标一组车道线地图，他认真阅读了地图可视化工具的对应接口，发现只要自己提供一组有序的点（Node）的坐标，工具就会依次连线画出一条车道线。
每一组点的首尾两点也被称作连接点（Connector），相邻车道的连接点的连线被称为连接线，输入有一组有序的连接点，工具就会依次连线画出一条连接线。
其中，连接线总是与车道线在该处的切线方向垂直。
他还发现，车道线的方向（汽车行驶的方向）也和这组点的排序方式以及对应连接点的排序方式有关：
设Pt是车道线最后一个点的坐标，Ph是车道线第一个点的坐标，Q_t是连接线最后一个点的坐标，Q_h是连接线第一个点的坐标，
则需满足对应连线形成的两个向量的叉积大于0
小林现在手头有的是一系列无序的坐标点的世界坐标（x,y）以及世界坐标下的朝向角（alpha），他想写一个函数，能将这些数据重新排序，使其满足上述的条件，
能够被地图可视化工具接受，请你帮帮他吧。

每个测试用例的第一行包含一个正整数N和正整数M，N代表车道线的数量，M代表每一条车道线上Node的数量。
接下来的N行，包含M个无序的坐标点（id, x, y, alpha）,分别代表点的id,x坐标，y坐标，朝向角

对于每组测试用例，输出N+2行结果，前N行表示对应的车道线Node排序后的结果，后两行分别表示该组车道线首尾的连接线上Node排序后的结果，使其能被地图可视化工具成功绘制，只需输出id即可

排序

这个题说实话没读特别明白，只看懂了需要把已知的车道节点按照某个规则排序，然后喂给可视化工具。从题干中的示例看出：每条车道的节点按照x坐标升序排列，而连接点（首尾节点分别排序）按照y坐标降序排列。由此写了个满足示例的排序规则，结果AC了

n, m = map(int, input().split())
lanes, heads, tails = [], [], []
for i in range(n):
    lanes.append([])
    arr = list(map(float, input().split()))
    for j in range(0, len(arr), 4):
        lanes[i].append([int(arr[j]), arr[j + 1], arr[j + 2], arr[j + 3]])
    lanes[i].sort(key=lambda x: x[1])      # 对车道节点按x坐标升序排列
    # 将车道节点的排列结果打印
    for node in lanes[i]:
        print(node[0], end=" ")
    print()
    # 记录当前车道的首尾节点
    heads.append(lanes[i][0])
    tails.append(lanes[i][-1])  heads.sort(key=lambda y: -y[2])
# 对连接点按照y坐标降序排列
tails.sort(key=lambda y: -y[2])
for head in heads:
    print(head[0], end=" ")
print()
for tail in tails:
    print(tail[0], end=" ")
print()

车道线大师

输入描述:

输出描述:

输入

输出

排序

问题信息

热门推荐

通过挑战的用户

相关试题