P17190 [ICPC 2017 Hong Kong R] Triangle

Bob 在平面中绘制了 $N$ 个黑点和 $N$ 个白点，并在每一对点之间绘制有向边。对于每一对点 $p$ 和 $q$，Bob 按照下述规则绘制边。 * 若两点颜色相同，则可选择绘制边 $p \to q$ 或 $q \to p$。 * 若两点颜色不同，不妨设 $p$ 为白点、$q$ 为黑点：如果 $\text{dist}(p, q) > D$ 则绘制边 $p \to q$，否则绘制边 $q \to p$。 距离函数定义为 $\text{dist}(p, q) = |p.x - q.x| + |p.y - q.y|$。 Bob 认为，一个由点 $p$、$q$ 和 $r$ 组成的 **美丽三角形**（即一个三点组）应满足以下条件： * 其中至少有一个黑点，至少有一个白点。 * $p \to q$、$q \to r$、$r \to p$ 是它们之间的全部边。 现在 Bob 想知道可能存在的美丽三角形的最小数量和最大数量。

输入包含多组测试数据，请处理到文件末尾。 对于每组测试数据，第一行包含两个整数 $N$ ($N \le 100000$) 和 $D$。接下来的 $N$ 行，每行包含两个整数，表示一个白点的坐标。再接下来的 $N$ 行，每行包含两个整数，表示一个黑点的坐标。一些点可能坐标相同。 输入中的所有数字均为非负整数且小于 $2^{31}$。

对于每组测试数据，输出两个整数，分别表示美丽三角形的最小可能数量和最大可能数量。

翻译由 DeepSeek V4 Pro 完成