#P18925. [2026多校联测]红蓝

[2026多校联测]红蓝

红蓝

B. 红蓝

题目描述

在平面直角坐标系上有 NN 个红色点和 MM 个蓝色点。给定自然数 WW 和 HH。

第 ii 个(1≤i≤N1\le i\le N)红色点的坐标是 (rxi,ryi)(r_{xi},r_{yi}),第 jj 个(1≤j≤M1\le j\le M)蓝色点的坐标是 (bxj,byj)(b_{xj},b_{yj})。所有点的坐标都不同。

我们需要放置一个宽度为 WW、高度为 HH 的矩形,该矩形的边与坐标轴平行,并且它的四个顶点是整数坐标。我们希望最大化矩形内包含的红色点与蓝色点数量之差,即∣红点数−蓝点数∣|\text{红点数}-\text{蓝点数}|。

矩形包含点的条件是:如果矩形的左下角坐标为 (a,b)(a,b),且点的坐标为 (x,y)(x,y),那么该点包含在矩形内当且仅当满足 a≤x≤a+Wa\le x\le a+W 且 b≤y≤b+Hb\le y\le b+H。

我们要求得这个差值的最大值,并找到符合这个最大差值的矩形位置。

下图展示了平面上有 3 个红色点和 4 个蓝色点的情况。为了说明问题,红色点用圆圈表示,蓝色点用三角形表示。

假设 W=5W=5、H=3H=3,那么如果将矩形的左下角放在 (3,3)(3,3),矩形内包含 1 个红色点和 3 个蓝色点,这时点的数量差为 2。无论矩形放置在哪里,点的数量差都不会大于 2,因此答案是 2。

输入格式

第一行给出整数 N,MN,M,以及矩形的宽度 WW 和高度 HH。

接下来的 NN 行,每行包含一个红色点的坐标 (rxi,ryi)(r_{xi},r_{yi})。

接下来的 MM 行,每行包含一个蓝色点的坐标 (bxj,byj)(b_{xj},b_{yj})。

输出格式

输出一个整数,表示最大点数差值。然后输出矩形左下角的坐标 (a,b)(a,b)。

如果答案有多个,输出任意一个即可。

样例 1

输入:

3 4 5 3
3 2
2 5
7 6
1 2
4 3
3 6
7 4

输出:

2
3 3

样例 2

输入:

3 3 4 4
1 1
2 2
3 3
1 3
3 1
4 4

输出:

2
-2 -2

数据范围与子任务

所有数据满足 1≤N,M≤1000001\le N,M\le 100000,1≤W,H≤1091\le W,H\le 10^9,红蓝点坐标均为正整数且不超过 10910^9。

子任务 分值 限制
1 5 N,M,W,HN,M,W,H 及所有坐标均不超过 5050
2 11 N,M,W,HN,M,W,H 及所有坐标均不超过 10001000
3 15 N,M≤100N,M\le 100
4 9 N,M≤1000N,M\le 1000
5 60 无额外限制