小欧在平面直角坐标系上有 n 个点(保证 n 是偶数),小欧想把这些点两两配对,一共可配 (n/2) 对。配对的两点连一条线段。若该线段和坐标轴有一个交点,则视为有1的权值。因此,和x轴和y轴都有交点则有2的权值。(特殊的,若该线段经过原点,也视为有2的权值)。小欧希望最终的权值之和尽可能大,你能帮帮她吗?
第一行输入一个正整数 n ,代表点的数量,保证是偶数。 接下来的 n 行,每行输入两个非零整数 x_i 和 y_i 。 2≤ n ≤ 10^5 -10^9 ≤ x_i,y_i ≤ 10^9 保证 x_i,y_i 不为零。保证没有两个点坐标相同。
输出一个整数,表示最大的权值。
2 1 1 -1 -1
2
4 1 1 -1 1 2 1 -2 1
2
考点:计算几何
数据规模 n ≤ 1e5 | 限制 1 秒 / 256MB | 标准输入输出
参考方向:计算几何
把几何关系转成坐标运算,用整数运算避免浮点误差。
思路框架(计算几何 通法 · 非本题专属)
实现要点:叉积 cross = x1*y2 - x2*y1;用它判断顺时针/逆时针和共线。
复杂度:时间 O(n) ~ O(n²) | 空间 O(n)
该范式的通法易错点
对照本题
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。
样例 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的权值。
解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:2023年OPPO秋招研发岗笔试。