LintCode: Rectangle

Posted on February 25, 2018July 26, 2020 by braindenny

Rectangle

Similar Problems:

Give a set, if you can find four points that make up a rectangle that is parallel to the coordinate axis and outputs YES or NO.

Notice
The number of points in the set is less than 2000, and the coordinate range is [-10000000,10000000].

Example

Given set = [[0,0],[0,1],[1,1],[1,0]], return YES.

Explanation:
We can find four points that make up a rectangle which is parallel to the coordinate axis.

Given set = [[0,0],[0,1],[1,1],[2,0]], return NO.

Explanation:
We can not find four points that meet the conditions

Github: code.dennyzhang.com

Credits To: LintCode.com

Leave me comments, if you have better ways to solve.

## https://code.dennyzhang.com/rectangle
#!/usr/bin/env python
"""
class Point:
    def __init__( self, x=0, y=0):
        self.x = x
        self.y = y
"""
class Solution:
    """
    @param pointSet: The point set
    @return: The answer
    """
    def rectangle(self, pointSet):
        ## Basic Ideas:
        ##   a, b, c
        ##   a*a+b*b=c*c
        ## Complexity: Time O(1), Space O(1)
        if len(pointSet) != 4: return 'NO'
        l = []
        for i in range(4):
            for j in range(4):
                if i == j: continue
                l.append(pow(pointSet[i].x-pointSet[j].x, 2)+pow(pointSet[i].y-pointSet[j].y, 2))
        mySet = set(l)
        count = len(mySet)
        # print(mySet)
        if count!=2 and count!=3: return 'NO'
        v1, v2 = min(mySet), max(mySet)
        c1, c2 = 0, 0
        for num in l:
            if num == v1: c1 += 1
            if num == v2: c2 += 1
        if len(l)%4 != 0 or c1%4 != 0 or c2%4 != 0: return 'NO'
        if count == 2:
            return 'YES' if v2 == 2*v1 else 'NO'
        else:
            v3 = None
            for num in mySet:
                if num != v1 and num !=v2: v3 = num
            return 'YES' if v2 == v1+v3 else 'NO'

Post Views: 6