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

小林最近打算标一组车道线地图，他认真阅读了地图可视化工具的对应接口，发现只要自己提供一组有序的点（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()

// js版本，我也没看懂题目意思 // 先按照x升序，获得每行的id排名 // 再按照y升序，获得头或者尾的排序 const [n, m] = readline().split(' ').map(Number); // arr: n * m * 4 let arr = []; // id: n * m const id = []; for (let i = 0; i < n; i++) { const temp = readline().split(' ').map(Number); let arrTmp = []; let idTmp = []; for (let j = 0; j < m; j++) { arrTmp.push(temp.slice(j * 4, j * 4 + 4)); } // 按照x的值升序排列 arrTmp = arrTmp.sort((a, b) => a[1] - b[1]); for (let j = 0; j < m; j++) { // 存储每行的id排序 idTmp.push(arrTmp[j][0]); } id.push(idTmp); // arr存储着每行的头和尾巴 n * m * 2 arr.push([arrTmp[0], arrTmp[m - 1]]); } for (let i = 0; i < n; i++) { // 每行打印 console.log(id[i].join(' ')); } // 按照y降序排列 arr = arr.sort((a, b) => b[0][2] - a[0][2]); // 遍历所有头、再是所有尾巴 for (let i = 0; i < 2; i++) { const temp = []; for (let j = 0; j < n; j++) { // 把每行的（头或尾）id打印下来 temp.push(arr[j][i][0]); } console.log(temp.join(' ')); }

#include<bits/stdc++.h> using namespace std; int main(){ int n,m; cin>>n>>m; vector<vector<vector<double>>> lanes(n,vector<vector<double>>(m,vector<double>(4,0))); for(auto& lane:lanes) for(auto& point:lane) cin>>point[0]>>point[1]>>point[2]>>point[3]; for(auto& lane:lanes) sort(lane.begin(),lane.end(),[](vector<double>& p1, vector<double>& p2){return p1[1]<p2[1];}); vector<vector<double>> headp; vector<vector<double>> rearp; for(auto& lane:lanes){ headp.push_back(lane.front()); rearp.push_back(lane.back()); } sort(headp.begin(),headp.end(),[](vector<double>& p1, vector<double>& p2){return p1[2]>p2[2];}); sort(rearp.begin(),rearp.end(),[](vector<double>& p1, vector<double>& p2){return p1[2]>p2[2];}); for(auto& lane:lanes){ for(auto& point:lane){ cout<<(int)point[0]<<' '; } cout<<endl; } for(auto& point:headp) cout<<(int)point[0]<<' '; cout<<endl; for(auto& point:rearp) cout<<(int)point[0]<<' '; cout<<endl; }

车道线大师

输入描述:

输出描述:

输入

输出

排序

问题信息

热门推荐

通过挑战的用户

相关试题