# LintCode: Rectangle

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.

```## Blog link: 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
"""
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'
```

Share It, If You Like It.