from math import sqrt,sin,cos,tan,asin,acos,atan2,pi,floor,gcd epsilon = 1e-8 def compare(x: float, y: float, ep: float = epsilon) -> int: """ x,y の大小比較をする. ただし, ep の誤差は同一視する. Args: x (float): y (float): ep (float, optional): 許容誤差. Defaults to epsilon. Returns: x > y のときは 1 x = y のときは 0 x < y のときは -1 """ diff = x - y if diff > ep: return 1 elif diff < -ep: return -1 else: return 0 def sign(x: float, ep: float = epsilon) -> int: if x > ep: return 1 elif x < -ep: return -1 else: return 0 def equal(x: float, y: float, ep: float = epsilon) -> bool: return abs(x - y) < ep class Point: __slots__ = ('x', 'y') def __init__(self, x: float = 0, y: float = 0): self.x = x self.y = y #文字列 def __str__(self): return f"({self.x}, {self.y})" def __repr__(self): return f"{self.__class__.__name__}({self.x}, {self.y})" #Bool def __bool__(self): return (sign(self.x) != 0) or (sign(self.y) != 0) #等号 def __eq__(self, other: "Point") -> bool: return equal(self.x, other.x) and equal(self.y, other.y) #不等号 def __ne__(self, other: "Point") -> bool: return not (self == other) #比較(<) def __lt__(self, other: "Point") -> bool: if (t := compare(self.x, other.x)): return t < 0 return compare(self.y, other.y) < 0 #比較(<=) def __le__(self, other: "Point") -> bool: return self < other or self == other #比較(>) def __gt__(self, other: "Point") -> bool: return other < self #比較(>=) def __ge__(self, other: "Point") -> bool: return other <= self #正と負 def __pos__(self) -> "Point": return self def __neg__(self) -> "Point": return Point(-self.x, -self.y) #加法 def __add__(self, other: "Point") -> "Point": return Point(self.x + other.x, self.y + other.y) def __iadd__(self, other: "Point") -> "Point": self.x += other.x self.y += other.y return self #減法 def __sub__(self, other: "Point") -> "Point": return Point(self.x - other.x, self.y - other.y) def __isub__(self, other: "Point") -> "Point": self.x -= other.x self.y -= other.y return self #乗法 def __mul__(self, other: "Point") -> "Point": x, y = self.x, self.y u, v = other.x, other.y return Point(x * u- y * v, x * v + y * u) def __imul__(self, other: "Point") -> "Point": return other * self def __rmul__(self, other: int | float) -> "Point": if isinstance(other, (int, float)): return Point(other * self.x, other * self.y) raise NotImplemented #除法 def __truediv__(self, other) -> "Point": if other == 0: raise ZeroDivisionError return Point(self.x / other, self.y / other) #絶対値 def __abs__(self) -> float: return sqrt(self.x * self.x + self.y * self.y) norm = __abs__ def norm_2(self) -> float: """ ノルムの 2 乗を求める Returns: float: ノルムの 2 乗 """ return self.x * self.x + self.y * self.y #回転 def rotate(self, theta: float) -> "Point": """ 原点中心に theta だけ回転させた後の点を求める. Args: theta (float): 回転角 Returns: Point: 回転後の点 """ x, y = self.x, self.y s, c = sin(theta), cos(theta) return Point(c * x - s * y , s * x + c * y) def __iter__(self): yield self.x yield self.y def __hash__(self): return hash((self.x,self.y)) def latticization(self, delta: float = 1e-7): """ 点が格子点に十分近いとき, この点を格子点の点として修正する. Args: delta (float, optional): 判断のための閾値. Defaults to 1e-7. """ if (abs(self.x - floor(self.x + 0.5)) < delta) and (abs(self.y-floor(self.y + 0.5)) < delta): self.x = floor(self.x+0.5) self.y = floor(self.y+0.5) def normalization(self): """ 向きをそのままに, 長さを 1 に変換する. """ r = abs(self) self.x /= r self.y /= r def normal_unit_vector(self) -> "Point": """ 単位法線ベクトルを求める. Returns: Point: 単位法線ベクトル """ assert self, ValueError d = self.norm() return Point(-self.y / d, self.x / d) def dot(self, other: "Point") -> float: """ 内積を求める Args: other (Point): Returns: Point: 内積 """ return self.x * other.x + self.y * other.y def det(self, other: "Point") -> float: """ 外積を求める Args: other (Point): Returns: float: 外積 """ return self.x * other.y - self.y * other.x def arg(self) -> float: """ 原点からみたこの点の偏角 Returns: float: 偏角 """ return atan2(self.y,self.x) def copy(self): return Point(self.x,self.y) def iSP(A: Point, B: Point, C: Point) -> int: """ A->B->C と進んだときの進行方向を見る. ※ B が中心 Args: A (Point): 始点 B (Point): 中継点 C (Point): 終点 Returns: int: 左折 (反時計回り): +1 右折 (時計回り): -1 C-A-B の順に並んでいる: -2 A-B-C の順に並んでいる: 2 A-C-B の順に並んでいる: 0 """ if (p := sign((B - A).det(C - A))) != 0: return p if sign((B - A).dot(C - A)) == -1: return -2 if sign((A - B).dot(C - B)) == -1: return 2 return 0 class Polygon: __slots__ = ("vertices", ) def __init__(self, *points: Point): self.vertices = list(points) def __str__(self): return f"[Polygon] {', '.join(map(str, self.vertices))}" def __repr__(self) -> str: return f"{self.__class__.__name__}({', '.join(map(repr, self.vertices))})" def area(self): S = 0 vertices = self.vertices for i in range(len(vertices) - 1): S += vertices[i].det(vertices[i + 1]) S += vertices[-1].det(vertices[0]) return abs(S) / 2 def Convex_Hull(S: list[Point], online = False) -> Polygon: """ S の凸包を求める Args: S (list[Point]): 点集合 online (bool, optional): False のとき, 内角が 180 度になるのを許容しない. Defaults to False. Returns: Polygon: S の凸包 """ def cover(reverse_flag): vertices = [] for P in (reversed(S) if reverse_flag else S): if not online and vertices and vertices[-1] == P: continue while len(vertices)>=2: m = iSP(vertices[-2], vertices[-1], P) if m == -1 or (not online and m == 2): vertices.pop() else: break vertices.append(P) return vertices S.sort() #上側 upper = cover(True) #下側 lower = cover(False) return Polygon(*(upper + lower[1:-1])) #================================================== def solve(): N = int(input()) P: list[Point] = [None] * N P_inv = {} for i in range(N): X, Y = map(int, input().split()) P[i] = Point(X, Y) P_inv[P[i]] = i C = Convex_Hull(P) M = len(C.vertices) ans = ['No'] * N if M == 2: # C が直線の場合 S, T = C.vertices i = P_inv[S]; j = P_inv[T] # (a, b) = (±1, 0), (0, ±1) を調べれば十分. for a, b in [(1, 0), (-1, 0), (0, 1), (0, -1)]: if a * S.x + b * S.y > a * T.x + b * T.y: ans[i] = f'{a} {b}' ans[j] = f'{-a} {-b}' else: # C が三角形以上の多角形のとき for j, S in enumerate(C.vertices): i = P_inv[S] v = C.vertices[(j + 1) % M] - C.vertices[(j - 1) % M] ans[i] = f'{v.y} {-v.x}' return "\n".join(ans) #================================================== import sys input=sys.stdin.readline write=sys.stdout.write T = int(input()) for _ in range(T): print(solve())