#957451 (PyPy3) No.3438 [Cherry 8th Tune D] 競プロは向いてない

• 問題: No.3438 [Cherry 8th Tune D] 競プロは向いてない
• ユーザー: 👑 Kazun
• 提出日時: 2024-03-03 23:40:31
• 言語: PyPy3 (7.3.17)
• 結果: AC
• 実行時間: 1,587 ms / 3,000 ms
• コード長: 8,739 bytes
• コンパイル時間: 207 ms
• コンパイル使用メモリ: 82,364 KB
• 実行使用メモリ: 125,336 KB
• 最終ジャッジ日時: 2026-01-23 20:52:17
• 合計ジャッジ時間: 134,995 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

ファイルパターン	結果
sample	AC * 1
other	AC * 33

ソースコード

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())