結果

問題 No.5009 Draw A Convex Polygon
ユーザー H3PO4H3PO4
提出日時 2022-12-02 22:27:22
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,084 bytes
コンパイル時間 315 ms
実行使用メモリ 260,232 KB
スコア 0
最終ジャッジ日時 2022-12-02 22:27:34
合計ジャッジ時間 8,516 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from math import gcd
from functools import cmp_to_key


# 偏角ソート https://nebocco.hatenablog.com/entry/2021/11/13/185816 から拝借しています。
def area(p):
    x, y = p
    if y < 0:
        return 3
    elif x < 0:
        return 2
    else:
        return 1


def arg_cmp(p, q):
    ap = area(p)
    aq = area(q)
    if ap < aq:
        return -1
    elif ap > aq:
        return 1
    else:
        px, py = p
        qx, qy = q
        z = px * qy - py * qx
        if z > 0:
            return -1
        elif z < 0:
            return 1
        else:
            return 0


lst = []
MAX = 650
for x in range(1, MAX):
    for y in range(1, MAX):
        if gcd(x, y) != 1:
            continue
        for dx, dy in ((1, 1), (1, -1), (-1, 1), (-1, -1)):
            lst.append((x * dx, y * dy))

SIZE = 10 ** 6
cur_x = 0
cur_y = 0
print(SIZE)
print(cur_x, cur_y)
for x, y in sorted(lst, key=cmp_to_key(arg_cmp))[:SIZE - 1]:
    cur_x += x
    cur_y += y
    # assert -10 ** 9 <= cur_x <= 10 ** 9
    # assert -10 ** 9 <= cur_y <= 10 ** 9
    print(cur_x, cur_y)
0