class Solution(object):
    def minAreaFreeRect_tle(self, points):
        """
        :type points: List[List[int]]
        :rtype: float
        """

        def dotProduct(a, b, c):
            baX, baY = b[0] - a[0], b[1] - a[1]
            caX, caY = c[0] - a[0], c[1] - a[1]  # bugfixed, typo
            return baX * caX + baY * caY  # bugfixed dot product

        def distance(a, b):
            # print (b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2
            return ((b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2) ** 0.5


        res, s = float('inf'), []

        for i in xrange(len(points)):
            for j in xrange(0, len(points)):
                if j == i:
                    continue
                for k in xrange(0, len(points)):
                    if k == i or k == j:
                        continue
                    if not dotProduct(points[i], points[j], points[k]):
                        for l in xrange(0, len(points)):
                            if l == k or l == i or l == j or sorted([i, j, k, l]) in s \
                                    or dotProduct(points[l], points[j], points[k]) \
                                    or dotProduct(points[j], points[i], points[l]):
                                continue
                            s.append(sorted([i, j, k, l]))
                            res = min(res,
                                      distance(points[i], points[j]) * distance(points[i], points[k]))

        return res if res < float('inf') else 0

    def minAreaFreeRect(self, points):
        """
        :type points: List[List[int]]
        :rtype: float
        """

        def dotProduct(a, b, c):
            baX, baY = b[0] - a[0], b[1] - a[1]
            caX, caY = c[0] - a[0], c[1] - a[1]  # bugfixed, typo
            return baX * caX + baY * caY  # bugfixed dot product

        def distance(a, b):
            # print (b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2
            return ((b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2) ** 0.5

        points.sort()
        res, s = float('inf'), []

        for i in xrange(len(points)):
            for j in xrange(i + 1, len(points)):
                for k in xrange(j + 1, len(points)):
                    if not dotProduct(points[i], points[j], points[k]):
                        for l in xrange(k + 1, len(points)):
                            if not dotProduct(points[l], points[j], points[k]) and \
                                    not dotProduct(points[j], points[i], points[l]):
                                res = min(res,
                                          distance(points[i], points[j]) * distance(points[i], points[k]))

        return res if res < float('inf') else 0


if __name__ == '__main__':
    print Solution().minAreaFreeRect([[1, 2], [2, 1], [1, 0], [0, 1]])
    print Solution().minAreaFreeRect([[0, 1], [2, 1], [1, 1], [1, 0], [2, 0]])
    print Solution().minAreaFreeRect([[0, 3], [1, 2], [3, 1], [1, 3], [2, 1]])
    print Solution().minAreaFreeRect([[3, 1], [1, 1], [0, 1], [2, 1], [3, 3], [3, 2], [0, 2], [2, 3]])
    print Solution().minAreaFreeRect([[3, 3], [2, 2], [0, 0], [2, 1], [3, 0], [1, 3], [3, 1], [0, 1]])
    print Solution().minAreaFreeRect([[0, 2], [0, 1], [3, 3], [1, 0], [2, 3], [1, 2], [1, 3]])
