結果

問題 No.3438 [Cherry 8th Tune D] 競プロは向いてない
コンテスト
ユーザー titia
提出日時 2026-01-27 08:01:17
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 2,532 ms / 3,000 ms
コード長 1,732 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 374 ms
コンパイル使用メモリ 82,208 KB
実行使用メモリ 128,200 KB
最終ジャッジ日時 2026-01-27 08:03:32
合計ジャッジ時間 97,321 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

from operator import itemgetter
from random import randint

def outer_product(x,y,z,w):
    return x*w-y*z

T=int(input())

for tests in range(T):
    N=int(input())
    P=[list(map(int,input().split())) for i in range(N)]

    P2=[]
    for x,y in P:
        P2.append((x,y))

    # 凸包（Andrew's monotone chain）

    P2.sort(key=itemgetter(1)) # 一番左下の点から始める。
    P2.sort(key=itemgetter(0))

    # 上側凸包と下側凸包
    Q1=[]
    Q2=[]

    for x,y in P2:
        while True:
            if len(Q1)<2:
                break
     
            s,t=Q1[-1]
            u,v=Q1[-2]
     
            if outer_product(u-s,v-t,x-u,y-v)<=0:
                Q1.pop()
            else:
                break
     
        Q1.append((x,y))
     
        while True:
            if len(Q2)<2:
                break
     
            s,t=Q2[-1]
            u,v=Q2[-2]
     
            if outer_product(u-s,v-t,x-u,y-v)>=0:
                Q2.pop()
            else:
                break
     
        Q2.append((x,y))


    Q2.reverse()
    Q=Q1+Q2[1:] # 上側凸包と下側凸包を結んで凸包が完成
    Q.pop()

    D=dict()

    for i in range(len(Q)):
        a,b=Q[i]

        c,d=Q[(i+1)%len(Q)]
        e,f=Q[(i-1)%len(Q)]

        while True:
            x=randint(-2*10**9,2*10**9)
            y=randint(-2*10**9,2*10**9)

            if a*x+b*y>c*x+d*y and a*x+b*y>e*x+f*y:
                D[a,b]=(x,y)
                break

    LANS=[]

    for i in range(len(P)):
        a,b=P[i]
        if (a,b) in D:
            x,y=D[a,b]
            LANS.append(str(x)+" "+str(y))
        else:
            LANS.append("No")

    print("\n".join(LANS))
0