前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 593. 有效的正方形(数学)

LeetCode 593. 有效的正方形(数学)

作者头像
Michael阿明
发布2020-07-13 15:50:20
3700
发布2020-07-13 15:50:20
举报
文章被收录于专栏:Michael阿明学习之路

1. 题目

给定二维空间中四点的坐标,返回四点是否可以构造一个正方形。

一个点的坐标(x,y)由一个有两个整数的整数数组表示。

代码语言:javascript
复制
示例:
输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
输出: True
 
注意:
所有输入整数都在 [-10000,10000] 范围内。
一个有效的正方形有四个等长的正长和四个等角(90度角)。
输入点没有顺序。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/valid-square 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • 4个点可以组成6条边,最长的两条是对角线
  • 排序后,前4条边相等,后2条边对角线相等
代码语言:javascript
复制
class Solution {	//C++
public:
    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        set<vector<int>> s;
    	vector<vector<int>> p = {p1,p2,p3,p4};
    	vector<int> d;
        for(auto& pi : p)
            s.insert(pi);
        if(s.size() < 4) return false;//有重合点
    	for(int i = 0, j; i < 3; ++i)
    		for(j = i+1; j < 4; ++j)
    			d.push_back(dis(p[i][0],p[i][1],p[j][0],p[j][1]));
		sort(d.begin(), d.end());
		return (d[0]==d[1]) && (d[1]==d[2]) && (d[2]==d[3]) && (d[4]==d[5]);
    }
    int dis(int x1, int y1, int x2, int y2)
    {
        return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
    }	
};

0 ms 26.6 MB

代码语言:javascript
复制
class Solution:# py3
    def validSquare(self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
        p = [p1,p2,p3,p4]
        d = []
        s = set(tuple(pi) for pi in p)
        if len(s) < 4:
            return False
        def dis(a,b,c,d):
            return (a-c)**2+(b-d)**2
        for i in range(3):
            for j in range(i+1, 4):
                d.append(dis(p[i][0],p[i][1],p[j][0],p[j][1]))
        d = sorted(d)
        return d[0]==d[1] and d[1]==d[2] and d[2]==d[3] and d[4]==d[5]

48 ms 13.8 MB

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/06/23 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 题目
  • 2. 解题
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档