QOJ.ac

QOJ

حد الوقت: 1.0 s حد الذاكرة: 64 MB مجموع النقاط: 100

#5329. 击倒

الإحصائيات

John 不会开车,但他还是不断地参加驾照考试。为此,他去了一个当地的农场,那里有 $N$ 面旗帜放置在地面上,第 $i$ 面旗帜的位置为 $(x_i, y_i)$。John 的目标是开车绕行,并尽可能少地撞倒旗帜。

John 的宿敌——教练,认为 John 会撞倒太多的旗帜并造成混乱。他决定用他古老的法杖固定住 John 汽车上的某一点,从而强迫 John 的汽车只能绕着那个固定点旋转。

形式化地,给定旗帜的数量、它们的位置以及四个数字 $X, Y, A$ 和 $B$,它们描述了一个矩形,其中 $(X, Y)$ 是矩形的左上角,$A$ 是矩形的宽,$B$ 是矩形的高(该矩形代表 John 的汽车)。你的目标是固定该矩形上的某一点,使得当矩形绕该固定点旋转时,被撞倒的旗帜数量尽可能少。如果旗帜在旋转过程中的任何时刻位于矩形内部或边界上,我们认为该旗帜被撞倒。请输出将被撞倒的旗帜数量。

输入格式

第一行包含一个自然数 $N$ ($1 \le N \le 10^5$),表示旗帜的数量。

第二行包含四个整数 $X, Y, A$ 和 $B$ ($-10^7 \le X, Y \le 10^7$),($2 \le A, B \le 10^7$,$A$ 和 $B$ 为偶数),描述 John 的汽车。

接下来的 $N$ 行,每行包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i, y_i \le 10^7$),描述旗帜的位置。

你可以假设旗帜最初严格位于汽车外部。

输出格式

仅输出一行,包含一个整数 $K$,表示当固定点的位置选择最优时,将被撞倒的旗帜数量。

样例

样例输入 1

5
-12 8 20 12
9 1
-9 -9
3 12
13 -4
-5 13

样例输出 1

2

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.