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

题目描述

在二维平面中给出 n 个点，第 i 个点的坐标为 (x_i,y_i) ，其点权为 v_i 。你可以以原点 (0,0) 为圆心放置一个圆。
设圆的半径为 r ，若某点满足 x_i^2+y_i^2≤ r^2 ，则认为该点被圆覆盖。请你计算：
要使被覆盖点的权值和不少于给定整数 S ，所需的最小半径 r 是多少？
若无论半径多大都无法达到权值下限，则输出 -1 。

输入输出

输入描述
第一行输入两个整数 n,S(1≤ n≤10^5,1≤ S≤10^14) ——点的数量与要求的权值下限。
接下来 n 行，第 i 行输入三个整数 x_i,y_i,v_i(-10^9≤ x_i,y_i≤10^9,0≤ v_i<2^31) ，描述第 i 个点的坐标与权值。
输出描述
若存在可行半径，在一行输出该最小半径 r ；否则输出 -1 。
设你的输出为 a ，答案为 b 。当且仅当
(|a-b|/max(1,|b|))<10^-6
时，你的答案将被判定为正确。

样例共 2 组

样例 1 · 当半径为 5 时， (0,1) 、 (-1,1) 、 (3,3) 、 (-4,3) 四个点被覆盖，权值和为 2+3+4+1=10 ，达到要求。
输入
5 10
0 1 2
-1 1 3
3 3 4
-4 3 1
5 -3 1
输出
5
样例 2 · 权值和无法达到10
输入
5 10
0 1 2
-1 1 3
3 3 2
-4 3 1
5 -3 1
输出
-1

算法解析依据一般

考点：计算几何

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

题目画像

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

解题思路

参考方向：计算几何

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

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

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

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

复杂度：时间 O(n) ~ O(n²) ｜ 空间 O(n)

该范式的通法易错点

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

对照本题

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

样例解读

样例 1：输入 5 10 / 0 1 2 / -1 1 3 / 3 3 4 / -4 3 1 / 5 -3 1 → 输出 5

当半径为 5 时， (0,1) 、 (-1,1) 、 (3,3) 、 (-4,3) 四个点被覆盖，权值和为 2+3+4+1=10 ，达到要求。

样例 2：输入 5 10 / 0 1 2 / -1 1 3 / 3 3 2 / -4 3 1 / 5 -3 1 → 输出 -1

权值和无法达到10

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2023年OPPO秋招前端岗笔试；华为机试编程模拟题9。

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