← 返回题目列表

AtCoder · masters2025_final_a

A. 协同垃圾分类(A)

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

故事

第二届大师锦标赛现场决赛刚刚结束。 会场内,地上散落着可燃垃圾、不可燃垃圾、可回收垃圾三种垃圾。

高桥负责收集可燃垃圾,青木负责收集不可燃垃圾。 他们每人双手拿着一个垃圾袋,在会场周围走动收集垃圾。

需要对垃圾进行适当分类:高桥应仅收集可燃垃圾,青木应仅收集不可燃垃圾。 可回收垃圾稍后将由专业服务人员收集,因此应留在原处。

你的任务是帮助他们在尽可能短的时间内收集所有可燃和不可燃垃圾。

问题陈述

在二维尺寸平面上 10^6 \times 10^6,有 X 可燃垃圾物品, Y 不可燃垃圾物品,以及 Z 可回收垃圾项目,每个项目代表一个点。 你要指示高桥和青木,让他们分别收集所有可燃垃圾和不可燃垃圾。

高桥和青木分别用左右手握住垃圾袋的两端,袋子的开口由连接两只手的线段表示。 设左右手当前位置为 分别是 p = (p_x, p_y) 和 q = (q_x, q_y)。在一次操作中,指针可以直线移动到新位置 p' = (p_x', p_y') 和 q' = (q_x', q_y').

此时, 全部 垃圾位于两个三角形之上或内部 \triangle pqp' 和 \triangle p'qq' 被收集并从飞机上移除。 通过重复此操作,可以移动垃圾袋来收集垃圾。

注意:当左右手的动作交叉时,收集的区域可能会显得违反直觉。 然而,在这个问题中,为了简单起见,操作被视为左手先移动,然后右手移动。

允许高桥和青木的四只手在同一坐标处重叠。 当三角形退化为线段时,例如当双手沿着同一路径一起移动时,位于线段上的垃圾被收集。

提示:三角形内点测试 是否有一个点 p 位于三角形内部或边界上 \triangle abc 可以使用以下Python代码作为示例来确定。 在这里, p[0] 和 p[1] 代表 x- 和 y- 点的坐标 分别是 p。 即使三角形退化为线段或单个点,此代码也能正常工作,并且由于它仅使用整数算术,因此它允许精确计算而不会出现舍入错误。
def orient(a, b, p):
    return (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0])

def contains(p, a, b, c):
    # degenerate (colinear) case
    if orient(a, b, c) == 0:
        if orient(a, b, p) != 0 or orient(a, c, p) != 0:
            return False
        xs = (a[0], b[0], c[0])
        ys = (a[1], b[1], c[1])
        return min(xs) <= p[0] <= max(xs) and min(ys) <= p[1] <= max(ys)

    # non‐degenerate: check same side of all edges
    c1 = orient(a, b, p)
    c2 = orient(b, c, p)
    c3 = orient(c, a, p)
    return (c1 >= 0 and c2 >= 0 and c3 >= 0) or (c1 <= 0 and c2 <= 0 and c3 <= 0)

垃圾袋足够大,高桥和青木的手臂也足够长,所以左右手可能会分开任意远。 四只手的初始位置可以从整数坐标中自由选择 (x, y) 满足 0 \leq x \leq 10^6,\ 0 \leq y \leq 10^6。 同样,目标坐标 每手牌的 (x, y) 也必须是满足相同条件的整数。

在你发出的每个指令中,高桥和青木都同时移动双手。 如果它们的收集区域重叠,这是允许的,但在这种情况下,高桥首先在重叠区域收集垃圾。 位于连接左手和右手初始位置的线段上的任何垃圾在第一次操作期间被收集。

移动双手所需的时间是其移动距离的总和。 由于高桥和青木总是同步行动,因此一条指令所花费的时间是两个单独时间中较大的一个。

具体来说,当你指示高桥将他的手从 p_1 to p_1' 和来自 q_1 to q_1',青木将双手从 p_2 to p_2' 和来自 q_2 to q_2',该操作所花费的时间为:

\[ \max(\mathrm{dist}(p_1, p_1') + \mathrm{dist}(q_1, q_1'),\ \mathrm{dist}(p_2, p_2') + \mathrm{dist}(q_2, q_2')) \]

在这里, \mathrm{dist}(p, q) 表示点之间的欧氏距离 p 和 q.

您最多可以发出 10000 说明。

您的目标是找到满足以下所有条件的指令序列,并且总时间尽可能短:

  • 高桥收集所有可燃垃圾。
  • 青木收集所有不可燃垃圾。
  • 他们都不收集任何可回收垃圾。

评分

让 X' 是高桥收集的可燃垃圾数量, Y' 为 Aoki 收集的不可燃垃圾数量,以及 Z' 是仍未收集的可回收垃圾数量。 让 T 是总时间。

分数计算如下:

  • If X' + Y' + Z' = X + Y + Z 和 T \leq 10^8,那么 \mathrm{round}\left(10^6 \times \left(1 + \log_2 \frac{10^8}{T} \right)\right)

  • If X' + Y' + Z' < X + Y + Z or T > 10^8,那么 \mathrm{round}\left(10^6 \times \frac{X' + Y' + Z'}{X + Y + Z} \right)

根据不同的输入生成方法,该问题分为三个子问题:A、B、C。 每个子问题包含 150 个测试用例,提交该子问题的总分是该子问题中所有测试用例得分的总和。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。

最终排名由各子题获得的最高分之和决定,赛后不进行系统测试。 如果有多支队伍获得相同分数,则无论提交时间如何,他们都将排名在同一位置。


输入

输入由标准输入按以下格式给出:

X Y Z
x_0 y_0
\vdots
x_{X+Y+Z-1} y_{X+Y+Z-1}
  • 可燃垃圾数量 X 固定为 X = 100.
  • 不可燃垃圾数量 Y 是 Y = 0 or Y = 100.
  • 可回收垃圾数量 Z 满足 0 \leq Z \leq 100.
  • 垃圾坐标以整数对形式给出 (x_i, y_i),其中所有值都满足 1 \leq x_i, y_i \leq 10^6 - 1.
  • 索引的对应关系 i 垃圾类型如下:
    • i = 0, \dots, X - 1: 可燃垃圾
    • i = X, \dots, X + Y - 1: 不可燃垃圾
    • i = X + Y, \dots, X + Y + Z - 1: 可回收垃圾
  • 任意两个垃圾项之间的欧氏距离保证至少为 10^3.
  • 对于以下四个条件中的每一个,都至少存在一个可燃垃圾项目 (x, y) 满足它。 这确保收集所有可燃垃圾至少需要 T \geq 2 \times 10^5 时间。
    • x \leq 4 \times 10^5 和 y \leq 4 \times 10^5
    • x \leq 4 \times 10^5 和 y \geq 6 \times 10^5
    • x \geq 6 \times 10^5 和 y \leq 4 \times 10^5
    • x \geq 6 \times 10^5 和 y \geq 6 \times 10^5

输出

设高桥的初始左右手位置为 (x_{0,0}, y_{0,0}) 和 (x_{0,1}, y_{0,1})分别是 青木的初始左右手位置为 (x_{0,2}, y_{0,2}) 和 (x_{0,3}, y_{0,3})。

让 K 是操作次数。 在 t第一次操作 (t = 1, 2, \dots, K), 高桥的左右手移动到 (x_{t,0}, y_{t,0}) 和 (x_{t,1}, y_{t,1})分别是 然后青木的左右手移动到 (x_{t,2}, y_{t,2}) 和 (x_{t,3}, y_{t,3})。

然后,按以下格式输出到标准输出。

x_{0,0} y_{0,0} x_{0,1} y_{0,1} x_{0,2} y_{0,2} x_{0,3} y_{0,3}
\vdots
x_{K,0} y_{K,0} x_{K,1} y_{K,1} x_{K,2} y_{K,2} x_{K,3} y_{K,3}

在某些输入中,可能没有不可燃垃圾,在这种情况下,Aoki 没有任务要执行。 例如,在这种情况下,您可以输出 x_{t,2} = y_{t,2} = x_{t,3} = y_{t,3} = 0 让青木在角落里等着。

输入生成

  • \mathrm{rand}(L, U): 生成一个均匀分布的随机整数 L 和 U (含)。
  • \mathrm{rand\_double}(L, U): 生成一个均匀分布的随机实数 L 和 U.
  • \mathrm{normal}(\mu, \sigma):从具有均值的正态分布生成随机实数 \mu 和标准差 \sigma.

不可燃垃圾的数量范围 Y 和可回收垃圾 Z 每个问题如下:

问题 Y Z
A 0 来自 10 to 100
B 100 0
C 100 来自 1 to 100

垃圾项目按照可燃垃圾 → 不可燃垃圾 → 可回收垃圾的顺序按以下顺序生成每种类型:

  1. 确定垃圾项目的数量 N 从指定范围内均匀随机。
  2. 确定簇的数量 n 使用 \mathrm{rand}(5,10).
  3. 对于每个集群 i = 1, \dots, n,生成以下参数:
    • 重量: w_i = \mathrm{rand\_double}(0, 1)
    • 中心坐标: cx_i, cy_i = \mathrm{rand}(200000, 800000)
    • 标准差: \sigma_{x,i}, \sigma_{y,i} = \mathrm{rand}(30000, 90000)
    • 旋转角度: \theta_i = \mathrm{rand\_double}(0, \pi)
  4. 重复以下过程 N 次生成 N 垃圾位置 (x, y):
    • 选择一个集群 i 随机,概率与其权重成正比 w_i.
    • 生成 x' = \mathrm{normal}(\sigma_{x,i})、y' = \mathrm{normal}(\sigma_{y,i}).
    • 计算坐标 (x, y) 如下: \[ x=\mathrm{round}(cx_i+\cos(\theta_i)\cdot x'-\sin(\theta_i)\cdot y')\\ y=\mathrm{round}(cy_i+\sin(\theta_i)\cdot x'+\cos(\theta_i)\cdot y') \]
    • 接受坐标 (x, y) 如果满足 1 \leq x, y \leq 10^6 - 1 并且至少 10^3 远离任何先前生成的垃圾项目(欧几里得距离)。否则,重试生成 (x, y).

如果产生的垃圾类型是可燃垃圾,请确保以下四个区域中每个区域至少有一件物品:

  • x \leq 4 \times 10^5 和 y \leq 4 \times 10^5
  • x \leq 4 \times 10^5 和 y \geq 6 \times 10^5
  • x \geq 6 \times 10^5 和 y \leq 4 \times 10^5
  • x \geq 6 \times 10^5 和 y \geq 6 \times 10^5

如果不满足此条件,请从集群生成步骤重新启动该过程。

关于问题C

对于问题 C,每个团队可以创建自己的输入并通过提交来覆盖默认输入。 请参阅问题 D 页面,了解有关如何提交输入的说明。

每个团队可以提交四个输入。在提交的四份意见中,随机选择一份并向所有团队公开,其余三份用于评审。

输入发布和评审开始预计在比赛开始后大约 3 小时 30 分钟进行。 系统准备就绪后,将向所有参与者发布公告。

对于任何不提交自己输入的团队,将根据前面描述的输入生成过程随机生成四个输入。

由于每个团队都知道他们提交的输入内容,因此可以预先计算相应的输出并将其嵌入到解决方案程序中。

可以根据需要多次提交问题 D。 但是,对于每个团队来说,只有最后提交的内容 180 分钟内 从比赛开始 接收 将使用 AC 进行评审。

工具(输入生成器和分数计算)

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