Input are Points

Algorithms
topic
Catalogue
  1. 1. Lies inside or outside
    1. 1.1. Point Lies inside or outside a polygon
  2. 2. TODO
    1. 2.1. 939. Minimum Area Rectangle

Lies inside or outside

Point Lies inside or outside a polygon

  1. Draw a horizontal line to the right of each point and extend it to infinity
  2. Count the number of times the line intersects with polygon edges.
  3. A point is inside the polygon if either count of intersections is odd or point lies on an edge of polygon. If none of the conditions is true, then point lies outside.

TODO

939. Minimum Area Rectangle

Given some points, please calculate the minimum Rectangle.
Height and width must be parallel to axes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def minAreaRect(self, points):
        pset = set()
        for x, y in points:
            pset.add((x, y))

        n = len(points)
        res = float('inf')
        for i in range(n):
            for j in range(i+1, n):
                x1, y1 = points[i]
                x2, y2 = points[j]
                if x1 == x2 or y1 == y2:
                    continue
                if (x1, y2) not in pset or (x2, y1) not in pset:
                    continue

                res = min(res, abs(x2-x1) * abs(y2-y1))
        return 0 if res == float('inf') else res

Share