# Path: tryalgo/range_minimum_query.py
# class RangeMinQuery:
#     """Range minimum query
# 
#     maintains a table t, can read/write items t[i],
#     and query range_min(i,k) = min{ t[i], t[i + 1], ..., t[k - 1]}
#     :complexity: all operations in O(log n), for n = len(t)
#     """
#     def __init__(self, t, INF=float('inf')):
#         self.INF = INF
#         self.N = 1
#         while self.N < len(t):                     # find size N
#             self.N *= 2
#         self.s = [self.INF] * (2 * self.N)
#         for i in range(len(t)):                    # store values of t
#             self.s[self.N + i] = t[i]              # in the leaf nodes
#         for p in range(self.N - 1, 0, -1):         # fill inner nodes
#             self.s[p] = min(self.s[2 * p], self.s[2 * p + 1])
# 
#     def __getitem__(self, i):
#         return self.s[self.N + i]
# 
#     def __setitem__(self, i, v):
#         """ sets t[i] to v.
#             :complexity: O(log len(t))
#         """
#         p = self.N + i
#         self.s[p] = v
#         p //= 2                                    # climb up the tree
#         while p > 0:                               # update node
#             self.s[p] = min(self.s[2 * p], self.s[2 * p + 1])
#             p //= 2
# 
#     def range_min(self, i, k):
#         """:returns:  min{ t[i], t[i + 1], ..., t[k - 1]}
#         :complexity: O(log len(t))
#         """
#         return self._range_min(1, 0, self.N, i, k)
# 
#     def _range_min(self, p, start, span, i, k):
#         """returns the minimum in t in the indexes [i, k) intersected
#            with [start, start + span).
#            p is the node associated to the later interval.
#         """
#         if start + span <= i or k <= start:        # disjoint intervals
#             return self.INF
#         if i <= start and start + span <= k:       # contained intervals
#             return self.s[p]
#         left = self._range_min(2 * p, start, span // 2,
#                                i, k)
#         right = self._range_min(2 * p + 1, start + span // 2, span // 2,
#                                 i, k)
#         return min(left, right)


from tryalgo.range_minimum_query import RangeMinQuery
def area(p):
    """Area of a polygone

    :param p: list of the points taken in any orientation,
              p[0] can differ from p[-1]
    :returns: area
    :complexity: linear
    """
    A = 0
    for i, _ in enumerate(p):
        A += p[i - 1][0] * p[i][1] - p[i][0] * p[i - 1][1]
    return A / 2.
# snip}


# snip{ is_simple
# pylint: disable=too-many-locals
def is_simple(polygon):
    """Test if a rectilinear polygon is is_simple

    :param polygon: list of points as (x,y) pairs along the closed polygon
    :returns: True if the segements do not intersect
    :complexity: O(n log n) for n=len(polygon)
    """
    n = len(polygon)
    order = list(range(n))
    order.sort(key=lambda i: polygon[i])         # lexicographic order
    rank_to_y = list(set(p[1] for p in polygon))
    rank_to_y.sort()
    y_to_rank = {y: rank for rank, y in enumerate(rank_to_y)}

# Path: tryalgo/range_minimum_query.py
# class RangeMinQuery:
#     """Range minimum query
# 
#     maintains a table t, can read/write items t[i],
#     and query range_min(i,k) = min{ t[i], t[i + 1], ..., t[k - 1]}
#     :complexity: all operations in O(log n), for n = len(t)
#     """
#     def __init__(self, t, INF=float('inf')):
#         self.INF = INF
#         self.N = 1
#         while self.N < len(t):                     # find size N
#             self.N *= 2
#         self.s = [self.INF] * (2 * self.N)
#         for i in range(len(t)):                    # store values of t
#             self.s[self.N + i] = t[i]              # in the leaf nodes
#         for p in range(self.N - 1, 0, -1):         # fill inner nodes
#             self.s[p] = min(self.s[2 * p], self.s[2 * p + 1])
# 
#     def __getitem__(self, i):
#         return self.s[self.N + i]
# 
#     def __setitem__(self, i, v):
#         """ sets t[i] to v.
#             :complexity: O(log len(t))
#         """
#         p = self.N + i
#         self.s[p] = v
#         p //= 2                                    # climb up the tree
#         while p > 0:                               # update node
#             self.s[p] = min(self.s[2 * p], self.s[2 * p + 1])
#             p //= 2
# 
#     def range_min(self, i, k):
#         """:returns:  min{ t[i], t[i + 1], ..., t[k - 1]}
#         :complexity: O(log len(t))
#         """
#         return self._range_min(1, 0, self.N, i, k)
# 
#     def _range_min(self, p, start, span, i, k):
#         """returns the minimum in t in the indexes [i, k) intersected
#            with [start, start + span).
#            p is the node associated to the later interval.
#         """
#         if start + span <= i or k <= start:        # disjoint intervals
#             return self.INF
#         if i <= start and start + span <= k:       # contained intervals
#             return self.s[p]
#         left = self._range_min(2 * p, start, span // 2,
#                                i, k)
#         right = self._range_min(2 * p + 1, start + span // 2, span // 2,
#                                 i, k)
#         return min(left, right)


# Path: tryalgo/polygon.py
from tryalgo.range_minimum_query import RangeMinQuery

def area(p):
    """Area of a polygone

    :param p: list of the points taken in any orientation,
              p[0] can differ from p[-1]
    :returns: area
    :complexity: linear
    """
    A = 0
    for i, _ in enumerate(p):
        A += p[i - 1][0] * p[i][1] - p[i][0] * p[i - 1][1]
    return A / 2.
# snip}


# snip{ is_simple
# pylint: disable=too-many-locals
def is_simple(polygon):
    """Test if a rectilinear polygon is is_simple

    :param polygon: list of points as (x,y) pairs along the closed polygon
    :returns: True if the segements do not intersect
    :complexity: O(n log n) for n=len(polygon)
    """
    n = len(polygon)
    order = list(range(n))
    order.sort(key=lambda i: polygon[i])         # lexicographic order
    rank_to_y = list(set(p[1] for p in polygon))
    rank_to_y.sort()
    y_to_rank = {y: rank for rank, y in enumerate(rank_to_y)}

    S = RangeMinQuery([0] * len(rank_to_y))      # sweep structure