QOJ.ac

QOJ

時間限制: 2 s 記憶體限制: 2048 MB 總分: 100

#7696. 树木森林

统计

你派遣了一个机器人进入森林,但它迷路了。它配备了一个传感器,可以探测到周围所有的树木,无论是否有遮挡,但不幸的是,在这片森林里,所有的树看起来都一样。你拥有一份森林中所有树木的地图,表示为 $(x, y)$ 坐标点。方便起见,由于这里曾经是一个树木农场,所有的树都位于整数坐标上,尽管并非所有坐标都有树。机器人的传感器会告诉你相对于机器人前方范围内每棵树的 $x$ 和 $y$ 距离。然而,机器人相对于地图的朝向是未知的,因此每个传感器读数都以一个元组(相对于机器人右侧的距离,相对于机器人前方的距离)给出,且两个值都可以为负,因为机器人可以向各个方向探测。幸运的是,机器人总是位于整数坐标上,且朝向平行于正 $x$ 轴、负 $x$ 轴、正 $y$ 轴或负 $y$ 轴,并且永远不会与树木处于同一位置。你能找出机器人的位置吗?

输入格式

输入的第一行包含三个整数:$n_t$(森林中树木的数量)、$n_s$(机器人探测到的树木数量)和 $r_{max}$(任何传感器读数的最大曼哈顿距离)。接下来的 $n_t$ 行,每行包含两个整数,表示全局坐标系中所有树木的 $(x, y)$ 位置。最后的 $n_s$ 行,每行包含两个整数。第 $i$ 个传感器读数中的第一个整数 $s_{i,x}$ 表示沿垂直于机器人朝向的轴到树的距离,第二个整数 $s_{i,y}$ 表示沿平行于机器人朝向的轴的距离。你可以假设对于所有 $i$,都有 $|s_{i,x}| + |s_{i,y}| \le r_{max}$。你还可以假设 $0 < n_t \le 5000$,$0 < n_s \le 1000$,$0 < r_{max} \le 1000$,且所有树木位置的坐标满足 $-100,000 \le x, y \le 100,000$。

输出格式

输出以下内容之一:机器人所在的 $x, y$ 位置,以空格分隔的两个整数;如果地图中没有任何位置能产生给定的传感器读数,则输出 “Impossible”;如果存在两个或多个不同的位置和/或朝向能产生给定的传感器读数,则输出 “Ambiguous”。

样例

样例输入 1

4 4 100
1 1
2 2
2 1
3 3
0 1
0 2
-1 2
-2 3

样例输出 1

0 1

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.