• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode963.最小面积矩形II|MinimumAreaRectangleII

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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,2],[2,1],[1,0],[0,1], with an area of 2.

Example 2:

Input: [[0,1],[2,1],[1,1],[1,0],[2,0]]
Output: 1.00000
Explanation: The minimum area rectangle occurs at [1,0],[1,1],[2,1],[2,0], with an area of 1.

Example 3:

Input: [[0,3],[1,2],[3,1],[1,3],[2,1]]
Output: 0
Explanation: There is no possible rectangle to form from these points.

Example 4:

Input: [[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [2,1],[2,3],[3,3],[3,1], with an area of 2.

Note:

  1. 1 <= points.length <= 50
  2. 0 <= points[i][0] <= 40000
  3. 0 <= points[i][1] <= 40000
  4. All points are distinct.
  5. Answers within 10^-5 of the actual value will be accepted as correct.

给定在 xy 平面上的一组点,确定由这些点组成的任何矩形的最小面积,其中矩形的边不一定平行于 x 轴和 y 轴。

如果没有任何矩形,就返回 0。

示例 1:

输入:[[1,2],[2,1],[1,0],[0,1]]
输出:2.00000
解释:最小面积的矩形出现在 [1,2],[2,1],[1,0],[0,1] 处,面积为 2。

示例 2:

输入:[[0,1],[2,1],[1,1],[1,0],[2,0]]
输出:1.00000
解释:最小面积的矩形出现在 [1,0],[1,1],[2,1],[2,0] 处,面积为 1。

示例 3:

输入:[[0,3],[1,2],[3,1],[1,3],[2,1]]
输出:0
解释:没法从这些点中组成任何矩形。

示例 4:

输入:[[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]
输出:2.00000
解释:最小面积的矩形出现在 [2,1],[2,3],[3,3],[3,1] 处,面积为 2。

提示:

  1. 1 <= points.length <= 50
  2. 0 <= points[i][0] <= 40000
  3. 0 <= points[i][1] <= 40000
  4. 所有的点都是不同的。
  5. 与真实值误差不超过 10^-5 的答案将视为正确结果。

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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift - 制作一个录音机(声音的录制与播放)发布时间:2022-07-13
下一篇:
swift监听键盘弹出的高度发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap