小欧的平面连线
小欧的平面连线
OPPO 笔试真题 · 2023 秋招 · 研发岗
判题请到牛客原题提交。
题目描述
小欧在平面直角坐标系上有个点（保证是偶数），小欧想把这些点两两配对，一共可配 对。配对的两点连一条线段。若该线段和坐标轴有一个交点，则视为有1的权值。因此，和x轴和y轴都有交点则有2的权值。（特殊的，若该线段经过原点，也视为有2的权值）。小欧希望最终的权值之和尽可能大，你能帮帮她吗？
输入格式
第一行输入一个正整数，代表点的数量，保证是偶数。
接下来的行，每行输入两个非零整数和。
保证不为零。保证没有两个点坐标相同。
输出格式
输出一个整数，表示最大的权值。
示例
示例 1
输入：
2
1 1
-1 -1输出：
2说明：
只有两个点，连一条线段经过原点，有2的权值。
示例 2
输入：
4
1 1
-1 1
2 1
-2 1输出：
2说明：
第一个点和第四个点连一条线段，和y轴交于(0,1)，贡献1的权值。
第二个点和第三个点连一条线段，和y轴交于(0,1)，贡献1的权值。
解题思路
第一步：理解问题本质
线段是否与坐标轴相交，可以完全用端点所在象限来判断，不需要真的求交点：
- 与 x 轴相交 ⟺ 两个端点的 y 坐标异号（一正一负，由连续性必然穿过 x 轴）；
- 与 y 轴相交 ⟺ 两个端点的 x 坐标异号。
题目保证 x、y 都不为 0，所以每个点都严格落在四个象限之一，不存在「点就在轴上」
这种边界情况。于是任意一对点的得分只有三种可能：
| 两个坐标 | 得分 |
|---|---|
| 都异号（对角象限） | 2 |
| 只有一个异号（相邻象限） | 1 |
| 都同号（同一个象限） | 0 |
特别地，线段经过原点时两个坐标当然都异号，按上表正好得 2 分，不需要单独判断。
第二步：把点按象限分成四类
记四类点的数量为
q_pp：(+, +)q_pn：(+, −)q_np：(−, +)q_nn：(−, −)
只有 (+,+) 与 (−,−) 配对、(+,−) 与 (−,+) 配对才能拿 2 分 ——
它们互为「对角」。同象限配对得 0 分，其余组合得 1 分。
第三步：先配 2 分，不会吃亏
能配出的 2 分对数最多是 min(q_pp, q_nn) + min(q_pn, q_np)。
可以放心先把它们配上，理由是：一对 2 分正好等价于两对 1 分
（都用掉 2 个点、都得 2 分）。也就是说，把能拿 2 分的点拆开去凑 1 分，
总分不会变高，先配 2 分至少不会更差。
第四步：剩下的用 1 分补
配完 2 分之后，每对互补象限里总有一类还剩一些点，记
r1 = |q_pp − q_nn|（残余集中在(+,+)或(−,−)这一组）r2 = |q_pn − q_np|（残余集中在(+,−)或(−,+)这一组）
这两组之间的任意两点，恰好只有一个坐标同号（一组是「同号组」，另一组是
「异号组」），所以配起来每对得 1 分，最多能配 min(r1, r2) 对。
再剩下的点全部属于同一类，只能得 0 分。n 是偶数，所以一定配得完。
最终答案：
2 * min(q_pp, q_nn) + 2 * min(q_pn, q_np) + min(r1, r2)完整代码实现
import sys
def solve() -> None:
"""按象限分类计数，先配互补类再配残余"""
data = list(map(int, sys.stdin.buffer.read().split()))
if not data:
return
n = data[0]
q = [0, 0, 0, 0] # 下标 (x 正?, y 正?) -> 象限计数
for i in range(n):
x = data[1 + 2 * i]
y = data[2 + 2 * i]
q[(1 if x > 0 else 0) * 2 + (1 if y > 0 else 0)] += 1
q_pp, q_pn, q_np, q_nn = q[3], q[1], q[2], q[0]
# 两个坐标都异号的互补配对，每对 2 分
ans = 2 * min(q_pp, q_nn) + 2 * min(q_pn, q_np)
# 残余之间恰好一个坐标异号，每对 1 分
r1 = abs(q_pp - q_nn)
r2 = abs(q_pn - q_np)
ans += min(r1, r2)
sys.stdout.write(str(ans) + "\n")
if __name__ == "__main__":
solve()示例推演
示例 1：(1,1) 与 (-1,-1)
| 点 | x 符号 | y 符号 | 类别 |
|---|---|---|---|
| (1, 1) | + | + | q_pp |
| (-1, -1) | − | − | q_nn |
q_pp = 1、q_nn = 1、q_pn = q_np = 0。
- 2 分对：
min(1, 1) + min(0, 0) = 1对 → 2 分 - 残余：
r1 = 0、r2 = 0→ 0 分
答案是 2。这一对点确实过原点，与说明一致。
示例 2：(1,1)、(-1,1)、(2,1)、(-2,1)
所有点的 y 都为正：
| 点 | 类别 |
|---|---|
| (1, 1) | q_pp |
| (2, 1) | q_pp |
| (-1, 1) | q_np |
| (-2, 1) | q_np |
q_pp = 2、q_np = 2、q_pn = q_nn = 0。
- 2 分对：
min(2, 0) + min(0, 2) = 0对 → 0 分 - 残余：
r1 = |2 − 0| = 2、r2 = |0 − 2| = 2→min(2, 2) = 2对 → 2 分
答案是 2。两条线段都只与 y 轴相交，各得 1 分，与说明一致。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 枚举全部配对方案 | O((n-1)!!) | O(n) | 配对数呈阶乘级，n = 10 就爆 |
| 按象限计数 + 贪心公式 | O(n) | O(1) | 推荐，只需一遍读入 |
易错点总结
1. 真的去算线段与坐标轴的交点
用解析几何求交点既慢又容易有精度问题，而且完全没有必要。
判断「是否相交」只需要两个端点坐标的符号，O(1) 就能得出。
2. 以为「过原点」要单独加一分
过原点的线段，两个坐标本来就都异号，按符号表已经得了 2 分。
再额外加分会超过每对的上限 2 分。
3. 担心「先配 2 分会亏」
有人会担心「把点配成 2 分之后，剩下的点只能配 0 分」。
注意一对 2 分等于两对 1 分，拆开去凑 1 分不会让总分更高，
所以贪心地先配对角象限是安全的。
4. 残余配对也能得 1 分
很多人配完 2 分就停了，把剩余点随便两两配对（很多是 0 分）。
而「同号组」的残余与「异号组」的残余之间，每对都能得 1 分，
还能再捞 min(r1, r2) 分。
5. 坐标范围的溢出顾虑
|x|, |y| 可达 10^9，但本题只用到符号比较，连坐标运算都不需要做；
即使需要，Python 的整数也不会溢出。
扩展思考
- 如果改成「越靠近原点得分越高」这类带权规则，就不能只按象限分类，
需要按方向排序后用双指针或匹配算法。 - 如果禁止同象限配对，就要先判断可行性：任一类点的数量都不超过
n / 2时
才存在「每对都跨象限」的完整配对，答案再按上面的公式计算。 - 这种「只看符号 / 只看相对位置」的降维手法在几何题里很常见：
判点在直线哪侧、判两向量夹角是否为钝角，都是同一个思路。