专栏首页Michael阿明学习之路LeetCode 593. 有效的正方形(数学)

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

1. 题目

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

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

示例:
输入: 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条边对角线相等
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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 第 28 场双周赛(505/2144,前23.6%)

    全国排名: 505 / 2144,23.6%;全球排名: 1944 / 8571,22.7%

    Michael阿明
  • LeetCode 223. 矩形面积

    Michael阿明
  • LeetCode 347. 前 K 个高频元素(哈希/优先队列)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/top-k-frequent-elements 著作...

    Michael阿明
  • HDU5036 Explosion(期望 bitset)

    首先根据期望的线性性,可以转化为求每个点的期望打开次数,又因为每个点最多会被打开一次,只要算每个点被打开的概率就行了

    attack
  • 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 H. Holy Grail 多源最短路

    用户2965768
  • 2038:[2009国家集训队]小Z的袜子(hose)

    用户2965768
  • HDU4609 3-idiots(生成函数)

    但是如果直接算合法的方案的话会出现一点问题。我们在算的时候维护了一个后缀和表示乘起来大于等于这个数的方案。我们要求的方案需要满足i < j < k,但是这样计算...

    attack
  • Topcoder SRM 698 Div1 250 RepeatString(dp)

    attack
  • CodeForces #549 Div.2 C Queen

    ShenduCC
  • 洛谷P4383 [八省联考2018]林克卡特树lct(DP凸优化/wqs二分)

    小L 最近沉迷于塞尔达传说:荒野之息(The Legend of Zelda: Breath of The Wild)无法自拔,他尤其喜欢游戏中的迷你挑战。

    attack

扫码关注云+社区

领取腾讯云代金券