QOJ.ac

QOJ

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

#10953. 好球区

Estadísticas

在棒球运动中,好球带(strike zone)是击球手如果不挥棒,棒球必须通过的空间区域。如果击球手不挥棒,而棒球未通过好球带,则被称为坏球(ball)。图 H.1 展示了棒球比赛中由球追踪设备捕捉到的棒球在击球区的位置。在比赛中,每个蓝色点被称为好球(strike),每个红色点被称为坏球(ball)。通过分析此类比赛的球追踪数据,我们可以定义一个代表该场比赛好球带的矩形区域。

图 H.1:棒球比赛中棒球在击球区的位置。蓝色点被称为好球,红色点被称为坏球。

在本题中,给定平面上的两个点集 $P_1$ 和 $P_2$,以及两个正整数常量 $c_1$ 和 $c_2$。你需要找到一个轴平行矩形 $R$,使得评估函数 $\text{eval}(R) = c_1 \times s - c_2 \times b$ 最大化,其中 $s$ 是 $P_1 \cap R$ 中的点数,$b$ 是 $P_2 \cap R$ 中的点数。

输入格式

程序从标准输入读取数据。输入的第一行包含一个整数 $n_1$ ($1 \le n_1 \le 1,000$),表示 $P_1$ 中的点数。接下来的 $n_1$ 行,每行包含两个整数,范围在 $-10^9$ 到 $10^9$ 之间,表示 $P_1$ 中一个点的坐标。下一行包含一个整数 $n_2$ ($1 \le n_2 \le 1,000$),表示 $P_2$ 中的点数。接下来的 $n_2$ 行,每行包含两个整数,范围在 $-10^9$ 到 $10^9$ 之间,表示 $P_2$ 中一个点的坐标。$P_1 \cup P_2$ 中没有任意两个点共享相同的 $x$ 或 $y$ 坐标。最后一行包含两个整数 $c_1$ 和 $c_2$,范围在 $1$ 到 $10,000$ 之间。

输出格式

程序将结果写入标准输出。输出一行,包含一个整数,即对于给定的 $c_1$ 和 $c_2$,在所有可能的轴平行矩形 $R$ 中,$\text{eval}(R)$ 的最大值。

样例

输入 1

2
-1 -1
4 4
2
0 0
2 2
5 2

输出 1

6

输入 2

3
0 5
3 3
8 -1
3
1 4
6 0
7 1
3 2

输出 2

4

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.