QOJ.ac

QOJ

Límite de tiempo: 1 s Límite de memoria: 512 MB Puntuación total: 100

#3430. 提升墙壁

Estadísticas

当地建筑公司需要你的帮助。他们正在建造一栋公寓楼,墙壁是预制的,并使用起重机吊装到位。建筑公司已经确定了 $n$ 个可能的起重机位置,并需要从中选择一些,使得每一面墙的中心都能被至少一台起重机覆盖。起重机非常昂贵,因此他们希望尽可能少地使用起重机。如果墙壁中心与起重机的距离不超过 $r$,则该起重机可以覆盖这面墙。

要建造的房屋是一个长为 $\ell$、宽为 $w$ 的矩形。

任务

求出覆盖所有四面墙中心所需的最少起重机数量。

图 C.1:此示例对应样例输入 1。

输入格式

第一行包含四个空格分隔的正整数 $\ell, w, n$ 和 $r$,它们均不超过 $30$。$\ell$ 和 $w$ 表示房屋的长和宽,$n$ 表示可能的起重机位置数量,$r$ 表示每台起重机的覆盖距离。

接下来有 $n$ 行,每行包含两个整数 $x$ 和 $y$ ($-100 \le x, y \le 100$),表示一个可能的起重机位置。坐标系的原点位于建筑物中心,$x$ 轴沿房屋长度方向。因此,四面墙的中心坐标分别为 $(-\ell/2, 0), (\ell/2, 0), (0, -w/2), (0, w/2)$。

输出格式

输出一个整数,表示覆盖所有墙面中心所需的最少起重机数量;如果无法覆盖所有墙面中心,则输出 Impossible

样例

输入 1

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

输出 1

2

输入 2

6 1 1 1
1 0

输出 2

Impossible

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.