結果

問題 No.5009 Draw A Convex Polygon
コンテスト
ユーザー rin204
提出日時 2022-12-02 01:05:10
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,453 bytes
コンパイル時間 267 ms
実行使用メモリ 238,160 KB
スコア 0
最終ジャッジ日時 2022-12-02 01:05:19
合計ジャッジ時間 8,496 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from math import gcd

class A:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __lt__(self, other):
        return self.x * other.y < other.x * self.y

D = []
dx = 1
dy = 2
while len(D) * 4 < 10 ** 6:
    if gcd(dx, dy) == 1:
        D.append(A(dx, dy))
        D.append(A(dy, dx))
    dx += 1
    if dx == dy:
        dx = 1
        dy += 1

D.sort()
xy = []
x = -10 ** 9
y = 0

for d in D:
    x += d.x
    y += d.y
    xy.append((x, y))

for d in D:
    x += d.y
    y -= d.x
    xy.append((x, y))

for d in D:
    x -= d.x
    y -= d.y
    xy.append((x, y))

for d in D:
    x -= d.y
    y += d.x
    xy.append((x, y))

print(len(xy), flush=True)
for x, y in xy:
    print(x, y, flush=True)
    assert -10 ** 9 <= x <= 10 ** 9
    assert -10 ** 9 <= y <= 10 ** 9
exit()
def cross3(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

# ps = [(x, y), ...]: ソートされた座標list
def convex_hull(ps):
    qs = []
    n = len(ps)
    for p in ps:
        # 一直線上で高々2点にする場合は ">=" にする
        while len(qs) > 1 and cross3(qs[-1], qs[-2], p) >= 0:
            qs.pop()
        qs.append(p)
    t = len(qs)
    for i in range(n - 2, -1, -1):
        p = ps[i]
        while len(qs) > t and cross3(qs[-1], qs[-2], p) >= 0:
            qs.pop()
        qs.append(p)
    qs.pop()
    return qs

n = len(xy)
xy.sort()
ret = convex_hull(xy)
assert len(ret) == n
0