#2219. 0417 t2
0417 t2
0417 t2
题目描述
预览输出 题目名称 亚空间航行 题目类型 传统型 输入 标准输入 输出 标准输出 每个测试点时限 2.0 秒 内存限制 512 MiB 子任务数目 7 测试点是否等分 否 预览输出 亚空间航行(F) 亚空间航行(F) 【题目背景】 2202 年,人类掌握了亚空间航行技术。 【题目描述】 当启动亚空间航行技术的时候,飞船会在宇宙中开凿出一条亚空间隧道,你可以将 其理解为平面上y = 0 和y = y0, (y0 > 0) 两条直线(和无穷远处)围成的区域,而飞船 的起止点在x 轴负半轴和正半轴无穷远处(近似的,你可以认为亚空间航行的起点和终 点分别在s = (−1018, 0) 和t = (1018, 0))。 然而正如宇宙不是均匀的而是遍布行星和黑洞一样,亚空间隧道中存在许多“奇 点”,每个奇点位于某个坐标(x, y), x ∈[0, 106], y ∈[0, y0] 。对于在其中飞行的飞船而言, 靠近他们是危险的。因此,智能化的飞控系统应当规划一条从起点到终点的航线,使飞 船在任意时刻离这些奇点足够远——也就是任意时刻离最近的奇点的距离尽量大。当然 了,你的航线也不能超出亚空间隧道的范围。形式化地,给定n, y0 和n 个亚空间隧道 中编号从1 到n 的奇点{pi = (xi, yi)}n i=1,你要求: φ : [0, 1] →R × [0, y0] ∈ 2 , s.t. φ(0) = s, φ(1) = t n C0(R) sup inf min i=1 d(φ(t), pi) (∗) t∈[0,1] 其中d : R2 × R2 →R 为平面上的欧几里得距离,即: p (x1 −x2)2 + (y1 −y2)2 d((x1, y1), (x2, y2)) = 除此之外,亚空间隧道中的奇点分布并不稳定,有时会扫描到新的奇点,有时则会 有旧的奇点消失。具体来讲,飞船的飞控系统会接收两类共m 次事件: • 第一类形如1 x y,表示飞船新扫描到一个位于(x, y) 的奇点,其编号为存在过 的奇点的编号的最大值+1(包括已经消失的奇点)。 • 第二类形如2 id,表示编号为id 的奇点消失了,此时保证标号为id 的奇点存在 且没有消失。 为了在星际市场中保持竞争力,一个强大的飞控系统应当在每次事件发生后重新计 算(∗) 的值。 【输入格式】 从标准输入读入数据。 输入的第一行包含三个正整数n, m, y0。 接下来n 行,其中第i ∈[1, n] 行包含两个整数(xi, yi) 表示一个编号为i 的奇点。 接下来m 行,每行形如1 x y 或2 id 表示一次事件。 第2 页 共3 页 预览输出 亚空间航行(F) 【输出格式】 输出到标准输出。 输出m + 1 行,其中第一行输出一个非负实数表示没有事件发生时的答案,接下来 m 行每行一个非负实数依次表示每个事件发生后的答案。 当且仅当你的输出和标准答案的相对误差或绝对误差不超过10−6 时会被认为答案 max{|a|,|b|,1} ≤10−6 时会被 |a−b| 正确。即设你的输出和标准答案分别为a, b > 0,则当且仅当 认为答案正确。 【样例1 输入】 1 1 1 1 0 0 2 1 1 3 【样例1 输出】 1 1 0.70710678118654752440084436210485 2 子任务编号 特殊性质 子任务分值 n ≤ m ≤ 1 0 3 5 2 300 15 无 0 3 3,000 4 300 300 20 仅有1 类型的操作 5 6 3,000 3,000 y0 = 1 10 无 7 对于所有数据保证:1 ≤n, m ≤3000, 1 ≤y0 ≤106, x ∈[0, 106], y ∈[0, y0]。 保证2 类型的事件中,编号为id 的奇点存在且没有消失。 第3 页 共3 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
1 1 1
0 0
1 1 1
1.000000
0.707107