結果

問題 No.5009 Draw A Convex Polygon
コンテスト
ユーザー H3PO4
提出日時 2022-12-02 22:32:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,649 ms / 2,600 ms
コード長 1,085 bytes
コンパイル時間 262 ms
実行使用メモリ 130,828 KB
スコア 218,540
平均クエリ数 218541.00
最終ジャッジ日時 2022-12-02 22:32:29
合計ジャッジ時間 4,426 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます

ソースコード

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 = 300
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 = len(lst)
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