K围最小面积平方
在一次采访中被问到。我们在二维平面上得到N个点x[0]，y[0]...... x[n-1]，y[n-1]和一个整数K。
我们需要找到最小面积平方，整数坐标为顶点，边平行于坐标轴。包围至少K个给定的N个点，没有点躺在正方形的边界上，即所有K个点都应该严格在正方形内。
我想到了经典的最小封闭矩形问题，但无法推导出至少K个点的情况。如何处理这个问题？提前谢谢。
共有1个答案
由于最小正方形的边长是由最小/最大x/y坐标之间的差值所限定的上限，因此我们可以对边长进行二进制搜索。因此，我们只需要考虑决策问题：对于给定长度L，测试是否存在具有至少k个点的边长度L的正方形。
这个决策问题相当于将n个边长为L的正方形放在每个点的中心，并确定重叠的最大数量（盒子排列的深度）是否相同。通过使用平面扫描技术，决策问题可以在O（n lg n）时间内解决，因此优化问题可以在O（n lg n lgu）时间内解决，其中U是边长的上限。
-
以下是问题陈述。 > 现在你必须找到一个包含所有三角形的平行四边形，并且面积最小。假设四条边的两条相对边平行于轴或轴（这是您的选择）。 我的方法是： 假设其中两个平行于轴。 那么这组三角形的最左边点和最右边点将位于平行四边形的两个相对边缘。现在我将画两条直线，它们穿过这些点，平行于轴。 这样，我发现了两个边缘，这并不难。现在我卡住了，不知道怎么找到另外两个。我想了很多，但是因为我无法理解，所以我把
-
面积图包括普通的面积图（area）及面积范围图（arearange），根据面积连接线的不同，又可以分为直线面积图（area、arearange）和曲线面积图（areaspline 及 areasplinerange）。 一、面积图 图4-3 Highcharts 面积图 面积图相关的配置参考 API 文档： 面积图配置：针对当前数据列有效 面积数据列配置 ：针对当前页面的所有面积数据列有效 1、曲
-
NowCoder 解题思路 快速选择 复杂度：O(N) + O(1) 只有当允许修改数组元素时才可以使用 快速排序的 partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。可以利用这个特性找出数组的第 K 个元素，这种找第 K 个元素的算法称为快速选择算法。 // jav
-
给定一个（未排序的）数组S和一些整数k，找到对的数量i， j使得S的范围[i... j] 我在一次采访中收到了这个问题，经过排序后只能得出一个O（nlogn）解。但是，有人告诉我有一个O（n）解。有什么想法吗？
-
一、题目 输入n个整数，找出其中最小的k个数。 例子说明： 例如输入4 、5 、1、6、2、7、3 、8 这8 个数字，则最小的4 个数字是1 、2、3 、4 二、解题思路 解法一：O(n)时间算法，只有可以修改输入数组时可用。 可以基于Partition函数来解决这个问题。如果基于数组的第k个数字来调整，使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。这样
-
我试图解决的问题是： 给定平面上可以以圆为中心的M个点的集合和N个需要被圆覆盖的线段的集合，求线段的最小面积圆覆盖。也就是说，求圆和中心（从M个点中选择）的半径，使得所有N条线段都被覆盖，圆的总面积最小化。 任何指向论文、代码或近似算法的指针都会很棒。