← 返回题目列表

AtCoder · masters2024_final_a

A. 有风无人机控制 (A)

中文机器翻译题面 查看原题

问题陈述

高桥想要在二维平面上操作飞行无人机并参观 N 目的地任意顺序。 让 x- 轴为东西向且 y- 轴为南北向。 无人机的飞行区域是 2\cdot 10^5\times 2\cdot 10^5 广场由四堵墙包围 x=-10^5,x=+10^5,y=-10^5,y=+10^5。 此外,除了这些外墙之外,内部还可以存在其他墙。

无人机有状态和位置 (x,y) 和速度 (v_x,v_y)。 位置和速度始终是整数值。 从初始位置状态开始 (s_x,s_y) 和速度 (0,0),每回合可以执行以下两种类型的操作之一。

  1. 加速度:指定整数向量 (a_x,a_y) 改变无人机的速度 (v_x,v_y) to (v_x+a_x,v_y+a_y)。必须满足 a_x^2+a_y^2\leq 500^2.
  2. 测量:指定非零整数向量 (b_x,b_y) 并测量距当前无人机位置的距离 (x,y) 到最近的墙壁 (b_x,b_y) 方向具有不确定性。必须满足 b_x^2+b_y^2\leq 10^{10}。从该点延伸一条射线 (x, y) 朝以下方向 (b_x, b_y) (光线穿过 (x+b_x,y+b_y))并计算欧氏距离 d = \sqrt{(x-x')^2 + (y-y')^2} 说到点子上 (x', y') 它第一次与墙相交的地方。结果值为 \mathrm{round}(d\times \alpha),其中 \alpha 是从正态分布中采样的值,平均值为 1 和标准差 \delta,作为输入参数给出。重新取样 \alpha if \alpha \leq 0。如果射线穿过墙壁的端点,则认为它已击中墙壁。但是,如果射线平行于墙壁,则不算作命中。

操作后,风导致无人机速度略有变化 (v_x, v_y)。根据输入参数 \epsilon,从均值正态分布中抽取两个样本 0 和标准差 \epsilon。对这些采样值进行四舍五入后,它们表示为 (f_x, f_y)。无人机的新速度变为 (v_x + f_x, v_y + f_y).

每回合结束时,当前位置更新为 (x+v_x, y+v_y) 基于速度 (v_x, v_y) 在那一刻。然而,如果线段连接 (x, y) 和 (x+v_x, y+v_y) 与墙壁相交(包括线段与墙壁平行的情况),则认为与墙壁碰撞,不进行位置更新;相反,速度被重置为 (0, 0)。保证无人机在初始状态下不与任何墙壁接触,并且在发生碰撞时,无人机返回到碰撞前的位置,确保无人机在与墙壁接触时不会开始移动。

如果没有与墙壁碰撞,则检查是否已到达任何目的地。目的地 (p_x, p_y)尚未被访问过,如果连接的线段之间的距离被认为已到达 (x, y) 和 (x+v_x, y+v_y) 并且目的地点为 1000 或更少。该距离定义为任意点之间的最小距离 q 位于段 S 和点 p.

您最多可以执行5000轮操作,访问所有目的地后操作立即完成。

评分

从初始分数开始 0,每回合分数变化如下。

  1. 分数减少 2.
  2. 如果无人机撞到墙壁,则分数额外减少 100。如果同时撞到多堵墙,分数只会减少 100.
  3. 如果有第一次到达的目的地,分数增加 1000 每一项。

直到经过 5000 圈或访问完所有目的地之前,当前得分最高的得分将作为测试用例的得分。

如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分之和将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。

输入和输出

首先,信息以以下格式从标准输入给出。

N M \epsilon \delta
s_x s_y
p_{x,0} p_{y,0}
\vdots
p_{x,N-1} p_{y,N-1}
l_{x,0} l_{y,0} r_{x,0} r_{y,0}
\vdots
l_{x,M-1} l_{y,M-1} r_{x,M-1} r_{y,M-1}
  • 目的地数量固定为 N=10 所有问题。
  • 墙数 M 排除周长满足 0\leq M\leq 10.
  • (s_x,s_y) 代表无人机的初始位置,满足 -10^5< s_x,s_y< 10^5。保证它不在墙上,包括外围。
  • (p_{x,i},p_{y,i}) 表示坐标 i第一个目的地,满意 -10^5\leq p_{x,i},p_{y,i}\leq 10^5。目的地可能与墙壁接触。对于每个目的地,保证到初始位置和/或其他目的地的距离至少为 5000.
  • 的 (l_{x,i},l_{y,i}) 和 (r_{x,i},r_{y,i}) 代表坐标 i第墙端点并满足 -10^5\leq l_{x,i},l_{y,i},r_{x,i},r_{y,i}\leq 10^5。该墙具有正长度,并且保证与周边以外的任何墙没有公共部分。它还保证与外周界的共同点不超过一个。从这些条件可以保证飞行区域内的所有点都可以在不穿墙的情况下到达。

读取上述信息后,重复以下过程最多 5000 转。

对于加速度,输出加速度矢量 (a_x,a_y) 按以下格式转换为标准输出。

A a_x a_y

对于测量,输出方向 (b_x,b_y) 按以下格式测量到标准输出。

S b_x b_y

仅当执行测量时,才会在标准输入的单行中给出表示测量结果的整数值。

输出后面必须跟有新行,并且您必须刷新标准输出。 否则,提交的内容可能会被判定为 TLE。 请注意,在访问完所有目的地之后或之后,判断程序将不会响应查询。 5000 查询已完成,因此等待响应可能会导致 TLE.

在回合结束时,有关无人机移动结果的信息从标准输入以以下格式给出。

c h
q_0 \cdots q_{h-1}

值 c 表示是否与墙壁碰撞,带有 c=1 如果它与墙壁碰撞,并且 c=0 如果没有。没有关于它与哪堵墙相撞的信息。 价值 h 表示本回合首次访问的目的地数量,每个目的地 下一行中的 q_i 是第一次访问的目的地的ID(0\leq q_i\leq N-1)。 如果 h=0,该行 q_i 被跳过而不是空行。

示例

t 输出 输入
先前信息
2 0 10.0 0.1
43722 -75332
79243 32532
44002 -77034
0
A 150 -400
0 0
1
S 0 1
168969
0 1
1
\vdots

输入生成

让 \mathrm{rand}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。

我们描述了所有问题的共同部分。 请参阅下面的“问题差异​​”部分,了解每个问题的具体部分。

的一代 s

生成 s_x=\mathrm{rand}(-99999,99999) 和 s_y=\mathrm{rand}(-99999,99999).

的一代 p_{x,i} p_{y,i}

对于每个 i,生成 p_{x,i}=\mathrm{rand}(-100000,100000) 和 p_{y,i}=\mathrm{rand}(-100000,100000)。 如果有一个点在 s or (p_{x,j}, p_{y,j}) 欧氏距离小于 5000,我们重新生成 (p_{x,i},p_{y,i}).

墙的生成

对于每个 i,按如下方式生成墙。

首先,生成 l_{x,i}=\mathrm{rand}(-90000,90000) 和 l_{y,i}=\mathrm{rand}(-90000,90000),那么 设置 r_{x,i}'=l_{x,i}+\mathrm{rand}(-100000,100000) 和 r_{y,i}'=l_{y,i}+\mathrm{rand}(-100000,100000)。 如果 (l_{x,i},l_{y,i})=(r_{x,i}',r_{y,i}'),我们重新生成 i第堵墙。 如果 r_{x,i}' 超出范围(r_{x,i}'<-100000 or 100000<r_{x,i}')和 r_{y,i}' 也超出范围,我们重新生成 i第堵墙。 否则,设置 r_{x,i}=\min(100000,\max(-100000,r_{x,i}')) 和 r_{y,i}=\min(100000,\max(-100000,r_{y,i}'))。 如果这堵墙 (l_{x,i},l_{y,i})-(r_{x,i},r_{y,i}) 与另一个先前生成的墙有共享点,或者如果初始位置 (s_x,s_y) 在这堵墙上,我们重新生成 i第墙。 否则,采用它作为 i第墙。

问题差异

问题 测试用例数量 M \epsilon \delta
A 60 0 \mathrm{rand}(1,100) \mathrm{rand}(1,20)\times 0.01
B 60 10 \mathrm{rand}(0,1) 0.01
C 80 \mathrm{rand}(1,10) \mathrm{rand}(1,100) \mathrm{rand}(1,20)\times 0.01

工具(输入生成器和本地测试器)

请注意,在比赛期间禁止在团队之外分享可视化结果或讨论解决方案/想法。

工具使用的输入/输出文件规范

提供给本地测试人员的输入文件包含随机数 \alpha 和 (f_x,f_y) 以以下格式放在先前信息的末尾。

\alpha_0
\vdots
\alpha_{4999}
f_{x,0} f_{y,0}
\vdots
f_{x,4999} f_{y,4999}

\alpha_t 是轮次测量的误差 t 和 (f_{x,t},f_{y,t}) 是转弯时风引起的速度变化 t.

您的程序可能会输出以以下开头的注释行 #。由于判断程序会忽略所有注释行,因此您可以提交按原样输出注释行的程序。 除了求解器程序的输出之外,本地测试器还会在每轮开始时输出以下注释行。

#p x y
#v v_x v_y

(x,y) 和 (v_x,v_y) 是无人机在本回合开始时的坐标和速度。