牛牛有 n 对黑色的木棍,长度分别为 a_1,a_2,...,a_n , n 对白色的木棍,长度分别为 b_1,b_2,...,b_n ,牛牛可以每次取走一对黑色的木棍和一对白色的木棍组成一个对边颜色相同,临边颜色不同的矩形,并计算出这个矩形的面积。每对木棍只能使用一次且不能将这对木棍拆开,牛牛能知道他能得到的所有矩形的总面积最大为多少。
第一行,一个整数 n(1≤ n ≤ 10^5) 。 第二行, n 个整数 a_1,a_2,...,a_n(1≤ a_i≤ 10^5) 。 第三行, n 个整数 b_1,b_2,...,b_n(1≤ b_i≤ 10^5) 。
输出一行一个整数表示牛牛能得到的所有矩形的总面积最大为多少。
5 1 5 2 4 3 3 1 1 2 1
29
考点:计算几何
数据规模 n ≤ 1e5 | 限制 1 秒 / 128MB | 标准输入输出
参考方向:计算几何
把几何关系转成坐标运算,用整数运算避免浮点误差。
思路框架(计算几何 通法 · 非本题专属)
实现要点:叉积 cross = x1*y2 - x2*y1;用它判断顺时针/逆时针和共线。
复杂度:时间 O(n) ~ O(n²) | 空间 O(n)
该范式的通法易错点
对照本题
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。
样例 1
5 / 1 5 2 4 3 / 3 1 1 2 129解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:贝壳找房2023届校招算法卷3。