OPPO · 计算几何 · 算法编程题
OPPO 计算几何 n ≤ 1e5 时限 1 秒 / 256 MB

题目描述

小欧在平面直角坐标系上有 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 · 只有两个点,连一条线段经过原点,有2的权值。
输入
2
1 1
-1 -1
输出
2
样例 2 · 第一个点和第四个点连一条线段,和y轴交于(0,1),贡献1的权值。 第二个点和第三个点连一条线段,和y轴交于(0,1),贡献1的权值。
输入
4
1 1
-1 1
2 1
-2 1
输出
2

算法解析依据一般

考点:计算几何

数据规模 n ≤ 1e5 | 限制 1 秒 / 256MB | 标准输入输出

题目画像

  • 数据规模:n ≤ 1e5
  • 元素值域:x_i ≤ 1e9,y_i ≤ 1e9(注意整数类型选择,避免溢出)
  • 复杂度门槛:只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

参考方向:计算几何

把几何关系转成坐标运算,用整数运算避免浮点误差。

思路框架(计算几何 通法 · 非本题专属)

  1. 把点、向量、线段用坐标表示。
  2. 几何判定(平行、垂直、共线、相交)尽量用叉积/点积的整数形式:叉积为 0 即共线。
  3. 距离用平方比较,避免开方带来的浮点误差。
  4. 面积用叉积(鞋带公式)计算。

实现要点:叉积 cross = x1*y2 - x2*y1;用它判断顺时针/逆时针和共线。

复杂度:时间 O(n) ~ O(n²) | 空间 O(n)

该范式的通法易错点

  • 用浮点相等判断几何关系(应用整数叉积)。
  • 没考虑三点共线、重合等退化情况。

对照本题

  • 数据规模 n ≤ 1e5,只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
  • 元素值域最大到 1e9 —— 求和 / 相乘时记得开 64 位整数。
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。

样例解读

样例 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秋招研发岗笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解