import math from bisect import bisect_left, bisect_right from typing import ClassVar, Generator, Optional class SortedMultiset[T]: size: int a: list[list[T]] BUCKET_RATIO: ClassVar[int] = 16 SPLIT_RATIO: ClassVar[int] = 24 def __init__(self) -> None: self.size = 0 self.a = [] def __init__(self, a: Generator[T]) -> None: self.__init__(list(a)) def __init__(self, a: list[T]) -> None: a_copy = [x for x in a] n = self.size = len(a_copy) if any(a_copy[i + 1] < a_copy[i] for i in range(n - 1)): a_copy.sort() num_bucket = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO))) self.a = [a_copy[n * i // num_bucket : n * (i + 1) // num_bucket] for i in range(num_bucket)] def __iter__(self) -> Generator[T]: for i in self.a: for j in i: yield j def __reversed__(self) -> Generator[T]: for i in reversed(self.a): for j in reversed(i): yield j def __eq__(self, other: 'SortedMultiset[T]') -> bool: if len(self) != len(other): return False for x, y in zip(self, other): if x != y: return False return True def __ne__(self, other: 'SortedMultiset[T]') -> bool: return not self.__eq__(other) def __len__(self) -> int: return self.size def __bool__(self) -> bool: return self.size > 0 def __repr__(self) -> str: return "SortedMultiset" + str(self.a) def __str__(self) -> str: s = str(list(self)) return "{" + s[1 : len(s) - 1] + "}" def _position(self, x: T) -> tuple[list[T], int, int]: for i, a in enumerate(self.a): if not (a[-1] < x): break return (a, i, bisect_left(a, x)) def __contains__(self, x: T) -> bool: if self.size == 0: return False a, _, i = self._position(x) return i != len(a) and a[i] == x def count(self, x: T) -> int: return self.index_right(x) - self.index(x) def add(self, x: T) -> None: if self.size == 0: self.a = [[x]] self.size = 1 return a, b, i = self._position(x) a.insert(i, x) self.size += 1 if len(a) > len(self.a) * self.SPLIT_RATIO: mid = len(a) >> 1 self.a[b:b+1] = [a[:mid], a[mid:]] def _pop(self, a: list[T], b: int, i: int) -> T: ans = a.pop(i) self.size -= 1 if not a: del self.a[b] return ans def discard(self, x: T) -> bool: if self.size == 0: return False a, b, i = self._position(x) if i == len(a) or a[i] != x: return False self._pop(a, b, i) return True def lt(self, x: T) -> Optional[T]: for a in reversed(self.a): if a[0] < x: return a[bisect_left(a, x) - 1] return None def le(self, x: T) -> Optional[T]: for a in reversed(self.a): if not (x < a[0]): return a[bisect_right(a, x) - 1] return None def gt(self, x: T) -> Optional[T]: for a in self.a: if x < a[-1]: return a[bisect_right(a, x)] return None def ge(self, x: T) -> Optional[T]: for a in self.a: if not (a[-1] < x): return a[bisect_left(a, x)] return None def __getitem__(self, i: int) -> T: if i < 0: for a in reversed(self.a): i += len(a) if i >= 0: return a[i] else: for a in self.a: if i < len(a): return a[i] i -= len(a) raise IndexError("index out of range") def pop(self, i: int = -1) -> T: if i < 0: for b, a in enumerate(reversed(self.a)): i += len(a) if i >= 0: return self._pop(a, ~b, i) else: for b, a in enumerate(self.a): if i < len(a): return self._pop(a, b, i) i -= len(a) raise IndexError("index out of range") def index(self, x: T) -> int: ans = 0 for a in self.a: if not (a[-1] < x): return ans + bisect_left(a, x) ans += len(a) return ans def index_right(self, x: T) -> int: ans = 0 for a in self.a: if x < a[-1]: return ans + bisect_right(a, x) ans += len(a) return ans #判定変えるならここかも class AnglePoint: x: int y: int area: int def __init__(self, x: int, y: int): if x == 0 and y == 0: self.x = 0 self.y = 0 self.area = 0 else: g = math.gcd(abs(x), abs(y)) self.x = x // g self.y = y // g if self.y > 0 or (self.y == 0 and self.x > 0): self.area = 0 else: self.area = 1 def __lt__(self, other: AnglePoint) -> bool: if self.area != other.area: return self.area < other.area return self.x * other.y - self.y * other.x > 0 def __eq__(self, other: AnglePoint) -> bool: return self.x == other.x and self.y == other.y def __le__(self, other: AnglePoint) -> bool: return self < other or self == other def __gt__(self, other: AnglePoint) -> bool: return not (self <= other) def __ge__(self, other: AnglePoint) -> bool: return not (self < other) nu = input().split() N = int(nu[0]) Q = int(nu[1]) mem: list[AnglePoint] = [] for _ in range(N): nu = input().split() X = int(nu[0]) Y = int(nu[1]) ap = AnglePoint(X, Y) mem.append(ap) L = SortedMultiset[AnglePoint](mem)