[Swift Weekly Contest 116]LeetCode963. 最小面积矩形 II | Min
发布时间：2020-12-14 05:08:44 所属栏目：百科 来源：网络整理
导读：Given a set of points in the xy-plane,determine the minimum area of?any?rectangle formed from these points,with sides?not necessarily parallel?to the x and y axes. If there isn‘t any rectangle,return 0. ? Example 1: Input: [[1,2],[2,1],[1
|
Given a set of points in the xy-plane,determine the minimum area of?any?rectangle formed from these points,with sides?not necessarily parallel?to the x and y axes. If there isn‘t any rectangle,return 0. ? Example 1:
Input: [[1,2],[2,1],[1,0],[0,1]]
Output: 2.00000 Explanation: The minimum area rectangle occurs at [1,with an area of 2.
Example 2:
Input: [[0,0]]
Output: 1.00000 Explanation: The minimum area rectangle occurs at [1,with an area of 1.
Example 3:
Input: [[0,3],[3,1]]
Output: 0 Explanation: There is no possible rectangle to form from these points.
Example 4:
Input: [[3,3]]
Output: 2.00000 Explanation: The minimum area rectangle occurs at [2,with an area of 2.
Note:
给定在 xy 平面上的一组点，确定由这些点组成的任何矩形的最小面积，其中矩形的边不一定平行于?x 轴和 y 轴。 如果没有任何矩形，就返回 0。 示例 1：
输入：[[1,1]] 输出：2.00000 解释：最小面积的矩形出现在 [1,1] 处，面积为 2。 示例 2：
输入：[[0,0]] 输出：1.00000 解释：最小面积的矩形出现在 [1,0] 处，面积为 1。 示例 3：
输入：[[0,1]] 输出：0 解释：没法从这些点中组成任何矩形。 示例 4：
输入：[[3,3]] 输出：2.00000 解释：最小面积的矩形出现在 [2,1] 处，面积为 2。 提示：
460ms 1 class Solution { 2 func minAreaFreeRect(_ points: [[Int]]) -> Double { 3 var ans:Double = -1 4 var set:Set<Int> = Set<Int>() 5 for p in points 6 { 7 set.insert((p[0] << 16) | p[1]) 8 } 9 10 var n:Int = points.count 11 for i in 0..<n 12 { 13 for j in 0..<n 14 { 15 var x0:Int = points[j][0] - points[i][0] 16 var y0:Int = points[j][1] - points[i][1] 17 if i != j 18 { 19 for k in 0..<n 20 { 21 if i != k && j != k 22 { 23 var x1:Int = points[k][0] - points[i][0] 24 var y1:Int = points[k][1] - points[i][1] 25 if x0 * x1 + y0 * y1 == 0 26 { 27 var x:Int = points[j][0] + points[k][0] - points[i][0] 28 var y:Int = points[j][1] + points[k][1] - points[i][1] 29 if set.contains((x << 16) | y) 30 { 31 var cur:Double = sqrt(Double(x0 * x0 + y0 * y0)) * sqrt(Double(x1 * x1 + y1 * y1)) 32 if ans < 0 || ans > cur 33 { 34 ans = cur 35 } 36 } 37 } 38 } 39 } 40 } 41 } 42 } 43 return ans < 0 ? 0 : ans 44 } 45 } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
