在查看接口文件后推断，如果本题下发的工程接口文件真的是实际评测使用的文件，且评测时只改变选手提交的代码一个文件，那么本题的工程文件存在极其致命的疏漏。通过作弊即可轻松拿到满分的成绩。因此本评测窗口目前的成绩只能作为参考，以后有心情再改工程文件吧，但是大概率懒得改了。

由于配置限制，本题只允许使用 C++ 进行提交，且评分方式进行修改（但是我们会将 C/Java/Python 的工程文件放在文件下载区供选手参考）。此外，本题工程文件编译时间较长，请耐心等待，且不要滥用评测资源~

时间限制： 5.0 秒

空间限制： 256 MB

题目背景

在低空数字经济时代，无人机（Unmanned Aerial Vehicle，简称 UAV）数据采集、存储及续航能力成为人们关注的焦点。在本题中你将设计低成本无人机数据采集方案。

题目描述

假设在一个平面矩形物联网区域中（长 $length$ 米 $\times$ 宽 $width$ 米）部署 $M$ 个传感器节点，每个节点 $i = 1,\cdots, M$ 位置坐标 $(x_i, y_i)$。派遣一架多旋翼无人机执行数据收集任务，无人机从驻点起飞，以一定高度飞行，最大飞行速度 $V_{\text{max}}$，驻点坐标为 $(0,0)$。在执行任务期间，无人机飞到传感器节点上空某点（称之为数据收集点）悬停，通信覆盖半径为 $D_{\text{max}}$ 米，即：与水平相距 $D_{\text{max}}$ 内的传感器节点建立通信链路。

传感器节点 $i$ 在时刻 $t_i$ 秒采集数据，在通信链路建立之后上传至无人机上。无人机在同一时刻最多可与 $N$ 个传感器节点进行通信，无人机飞到某个悬停点，向 $N$ 个传感器节点 $i_1, \cdots, i_N$ 下发数据收集信令，节点 $i(i \in {i_1,\cdots, i_N})$ 收到这个信令后采集数据（采集时刻标记为 $t_i$），再通过无线信道上传给无人机。为简化模型，从建立通信链路到完成一次数据传输的时间设为 $T_{\text{com}} = 1$ 秒。若无人机在某个悬停点的通信范围内可采集节点数超过 $N$ 个（此时将可采集节点数设为 $S$），则需要分批采集数据，共分 $\lceil S/N\rceil$ 批，无人机悬停采集数据的总时间可表示为 $T_{\text{hover}} = \lceil S/N \rceil \times T_{\text{com}}$，其到达和离开时刻分别标记为 $(t_{\text{arr}}, t_{\text{dep}})$，其中，$t_{\text{dep}} = t_{\text{arr}} + T_{\text{hover}}$。注意，第 1、2、3 批节点的采集时刻可分别记为 $t_i = t_{\text{arr}}$、$t_i = t_{\text{arr}}+T_{\text{com}}$ 和 $t_i = t_{\text{arr}}+2T_{\text{com}}$。无人机执行完收集任务之后需飞回驻点，向数据中心卸载已采集的传感器节点数据；无人机能量不足时也需要及时飞回驻点补充能量，同时卸载已采集的传感器节点数据。

无人机在驻点出发时有满额能量 $E_\text{max}$，其飞行耗电量与其自身重量、飞行速度等很多因素有关。为简化模型，仅考虑无人机在水平飞行和悬停期间的能量消耗，不考虑其加速、减速、上升和下降过程中的时间和能耗。设某款多旋翼无人机的水平推进功率为：

$$P(v)=P_0\cdot(1+a\cdot v^2)+b\cdot v^3+P_1\cdot \sqrt{\sqrt{1+c\cdot v^4}-d\cdot v^2} \tag{1} $$

其中，$v$ 是无人机的水平飞行速度，$P_0 = 79.8563,~P_1 = 88.6279,~a = 0.00021,~b=0.00924,~c = 0.00073,~d =0.02704$ 都为系统常数。无人机能耗可以表示为推进功率 $P(v) \times$ 速度 $v$ 飞行的时间，其悬停能耗类似可以记为悬停功率$P(0)\times$ 悬停时间。因此，无人机沿着某条路径飞行并收集数据的能耗可以表示为每一段路径的飞行能耗与在每个悬停点的悬停能耗的和。考虑到无人机所携带电池容量有限，无人机可以飞回驻点进行充电，卸载已采集的传感器节点数据，再飞回去继续采集节点数据。在任务执行期间每次回到驻点充电并卸载数据的时间设为 $T_\text{charge} = 120$ 秒，此处假设无人机充电时间与其剩余能耗无关。

每个传感器节点的数据只需收集一次，不考虑重复数据收集。若传感器节点 $i$ 的数据在时刻 $t_i$ 采集，在 $T_i$ 卸载，则产生的潜在经济效益为 $\dfrac{R_i}{T_i-t_i}$ 元。其中 $R_i$ 是节点 $i$ 的收益参数。无人机在飞行数据收集期间的折旧成本与工作总时长 $t_\text{uav}$ 有关，计为 $L_\text{uav}=\alpha \times t_\text{uav}$，其中 $\alpha$ 是单位时间折旧价格，即折旧价格系数。

总收益公式为：$\sum\limits_{i=1}^M \dfrac{R_i}{T_i-t_i}-\alpha \times t_\text{uav}$。

请根据物联网数据采集需求、无人机能耗与充电动作，设计一个智能的物联网数据收集方案，通过优化无人机悬停点位置及规划无人机沿着悬停点飞行及收集传感器节点数据的路径，使得系统总收益最大。

其他假设

1. 无人机在执行数据收集任务期间，可以多次往返驻点，卸载清空缓冲区数据并充电；
2. 应考虑无人机在收集数据期间的悬停能耗；
3. 忽略无人机在起飞、降落、加速、减速过程中的时间和能耗；
4. 不考虑无人机在空中飞行转向能耗与路径长度；
5. 不考虑无人机飞行高度对能量消耗与数据传输时间的影响；
6. 不计入通信链路建立与删除时间。

输入数据

调试样例共 5 组，对选手公开，供本地调试程序使用；本评测窗口直接采用这 5 组调试样例进行评分，因此分数仅供参考。

每组样例的格式如下，每行的多个数据之间以空格隔开：

• 第 $1$ 行：区域长度 $length$，区域宽度 $width$，无人机电池容量 $E_\text{max}$，节点总数 $M$，可同时通信节点数 $N$；
• 接下来 $M$ 行为传感器节点数据
  • 第 $2$ 行：传感节电器 $1$ 的横坐标 $x_1$，纵坐标 $y_1$，收益系数 $R_1$；
  • 第 $3$ 行：传感节电器 $2$ 的横坐标 $x_2$，纵坐标 $y_2$，收益系数 $R_2$；
  • $\cdots$
  • 第 $M+1$ 行：传感器节点 $M$ 的横坐标 $x_M$，纵坐标 $y_M$，收益系数 $R_M$；

白盒样例范围如下：

测试点编号	$length=$	$width=$	$E_\text{max}=$	$M=$	$N=$
$1$	$2000$		$10^5$	$30$	$1$
$2$					$5$
$3$			$7\times 10^5$	$50$	$2$
$4$	$10^4$		$2\times 10^6$		$5$
$5$			$10^6$	$100$

系统的初始化常数参数直接在程序框架中定义，不在输入数据中，见下表：

系统参数	数值	程序中变量
无人机最大飞行速度	$V_{\text{max}}=30$ 米/秒	V_max
通信覆盖半径	$D_{\text{max}}=300$ 米	D_max
一次数据传输的时间	$T_{\text{com}}=1$ 秒	T_com
充电（包含卸载数据）的时间	$T_\text{charge}=120$ 秒	T_charge
折旧价格系数	$\alpha = 0.1$	alpha
驻点坐标	$(0,0)$	init_location
公式 $(1)$ 中各个变量	$P_0 = 79.8563,~P_1 = 88.6279,\\a = 0.00021,~b=0.00924,\\c = 0.00073,~d =0.02704$	P0,P1,a,b,c,d

输出格式

输出物联网数据收集系统的总收益与路径规划，包括：

• 总收益；
• 无人机的飞行路径（起飞与结束都回到驻点位置）信息，包括：
  • 一共几个悬停点（考虑从驻点出发和返回驻点，也考虑中途返回驻点的次数）；
  • 每个数据收集点的坐标（按飞过的顺序排序，在驻点不收集节点数据）；
  • 在每个悬停点的到达和离开时间；
  • 在每个数据收集点收集了哪些传感器节点的数据（提供节点序号列表）。

具体来说，无人机在 $0$ 时刻从驻点出发，本次的到达和离开时间记为 $(0,0)$。若最后返回到驻点的时刻为 $t$，则本次在驻点的到达和离开时间记为 $t,t$。若在某个数据收集点 $P_1$ 的到达和离开时间为 $(t_1,t_2)$，则时间差 $t_2-t_1$ 为在该点的总数据采集时间。若在下一个数据收集点 $P_2$ 的到达和离开时间为 $(t_3,t_4)$，则 $t_3-t_2$ 为无人机从 $P_1$ 到 $P_2$ 的飞行时间。在任务执行中回到驻点充电和卸载数据，相应的到达和离开时间为 $(t, t+ T_\text{charge})$。

以 Python 语言为例，选手的程序需要计算如下信息：总收益 profits，由程序返回；无人机飞行轨迹中的悬停点位置（包括数据收集点和驻点）列表，存放在 path 列表中；到达和离开每个悬停点的时间列表，存放在 timelabel 列表中；在每个悬停点所访问的传感器节点列表（不收集数据则用空表表示），存放在 sensor_visited 列表中。如果找不到满足要求的数据收集轨迹可将 profits 设为 $0$，列表设为空表。

样例：假设有 10 个传感器节点，选手的程序输出的无人机飞行轨迹从驻点出发，停留两个数据收集点，然后返回驻点。输出结果提供了如下信息（注意该样例仅提示数据格式，不体现数据间的对应关系，以下数据为 Python 格式）。

profits = 18.2 # 总收益，由程序返回
UAVpath = (4, # 悬停点数目，取自 path 列表长度
[(0,0), (10,10), (15,12), (0,0)], # 无人机轨迹，取自 path 列表
[(0,0), (5.05,7.05), (15.4,18.4), (20.5,20.5)], # 到达和离开时间，取自 timelabel 列表
[[], [3, 5, 1, 8], [2, 4, 9, 6, 7, 10], []] # 访问的传感器节点，取自 sensor_visited 列表
)

编程和调试说明：

再以 C 语言为例，main.c 搭建输入输出框架，读取 .in 文件数据并对系统进行初始化，调用选手程序得到输出结果，检查结果是否满足约束条件并计算总收益，最后从 .out 文件读取基线算法收益，给出本测试样例的评分。头文件 path_optimizer.h 定义了系统参数和一些必要的结构。

选手需完成 path_optimizer.c 中的 path_optimizer_run 函数，也可以对 path_optimizer.c 的其它部分根据自己的需要进行修改，注意数据和接口格式。测试时 path_optimizer.c 会被替换为选手的代码，其它文件不变。特别地，在 C 语言中飞行轨迹的长度需要选手自行保存在 num_pos 变量中，不取自列表长度。

选手完成 path_optimizer.c 后可用本地的 main.c 进行调试，也可基于 main.c 和 path_optimizer.h 自行编写测试程序帮助调试，最终只提交 path_optimizer.c。其它三种语言的调试和提交方式类似，需要完成并提交的部分分别在 path_optimizer.cpp，path_optimizer.py 和 PathOptimizer.java 中，相关的类或结构为 PathOptimizer。

输出结果的约束条件如下：

1. 无人机需收集所有节点的数据，每个节点仅被收集一次，不重复不遗漏；
2. 无人机在驻点不收集节点数据；
3. 在飞行途中每个数据收集点或驻点的停留时间（=离开时间-到达时间）满足：
   • 最初从驻点出发或最终返回驻点时，在驻点的停留时间为 $0$；
   • 在每个数据收集点停留时间大于 $0$，且等于在该点收集数据需要的总时间；
   • 返回驻点充电并卸载数据时，在驻点的停留时间为 $T_\text{charge} = 120$ 秒；
4. 无人机在驻点外的任意位置能量大于 $0$；
5. 无人机在任意位置飞行速度不大于其最大速度 $V_\text{max} = 30$ 米/秒；
6. 无人机在数据收集点需满足：
   • 在同一批次最多可与 $N$ 个传感器节点进行通信；
   • 数据收集点在平面矩形物联网范围内，即 $(x,y):0\le x\le length,0\le y\le width$；
   • 数据收集点到所收集的每个传感器节点的水平距离不超过 $D_\text{max}$；
7. 输出结果满足格式要求，与 main 函数中的格式检查相吻合。如下举例说明：
   • 从驻点出发时，对应的出发和离开时间为 $(0, 0)$；
   • 对于每个数据收集点收集的传感器节点列表，默认的收集顺序如下。假设某个数据收集点的传感器节点列表为 $\{2, 1, 4, 3, 5\}$，且 $N = 2$，则认为无人机第一次收集节点 $\{2\}$ 的数据，第二次收集节点 $\{1, 4\}$ 的数据，第三次收集节点 $\{3, 5\}$ 的数据。（这样可尽量减少列表中节点的卸载和收集的时间差。）

评分方式

本评测链接的计算方式相较于实际比赛有所调整。

对于每个测试点，输出结果不符合要求得 $0$ 分，符合要求则获得 $100$ 的正确分。假设选手程序的输出结果计算总收益为 $x$，基线算法的总收益为 $y$，那么该测试点的性能分为 $\frac{x}{y}\times 0.9\times 200$，超过 $200$ 的按 $200$ 计。对于输出结果符合要求的数据，其得分为正确分与性能分的总和。

工程文件下载

代码内的中文注释在查看时可能存在乱码，请使用 UTF-8 编码方式打开文件。

• C++ 工程文件
• C 工程文件
• Java 工程文件
• Python 工程文件