问题描述
给定10w辆出租车的经纬度和车厢乘客终点，并给定一个乘客的起止位置，找出绕路不超过10km且距离乘客不超过10km的最多五辆车。
方法
实现分成三步：
- 预处理阶段：预处理出一辆车上任意两人距离，以及每辆车将乘客依次送达目的地的路程D1；
- 遍历出租车，筛去离乘客距离超过10km的出租车；
- 剩下的出租车，计算接乘客路程D2,、接到乘客后依次送达的距离D3、待接乘客离自己目的地的最短距离D4。然后计算绕路距离，不超过10km的留下。
在实现中，使用metis库计算路网中的数据，包括建树和计算两点间最短距离。
完成功能
- 输入一个乘客位置，在可以忍受的时间内返回不超过5个有空位的出租车。所有返回的出租车与乘客距离不超过10km，若没有合适的出租车，则返回空列表；
- 返回的所有出租车的绕路距离不超过10km；
- 提供UI界面方便输入输出的交互；
- 使用路网数据完成大作业；
- （加分项） 给出建议路线。
运行方式
使用的第三方库为metis和Qt。请使用qmake或Qt Creator运行程序。程序界面如下：
image.png
图中右侧输入乘客起止坐标，点击search按钮即可获得最近的满足条件的（最多）五辆出租车。下面列出了五辆车的ID和距离乘客的距离，以及给该出租车规划的路线。点击show按钮即可查看规划路线，其中绿点表示乘客的起始坐标，红点表示乘客的终止坐标；深橙色的点表示出租车的位置，浅橙色的点为车上所有乘客的下车坐标。蓝色为路线。
网友评论