結果

問題 No.5009 Draw A Convex Polygon
コンテスト
ユーザー 👑 SPD_9X2
提出日時 2022-12-02 01:01:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,253 ms / 2,600 ms
コード長 1,699 bytes
コンパイル時間 679 ms
実行使用メモリ 246,760 KB
スコア 254,196
平均クエリ数 254197.00
最終ジャッジ日時 2022-12-02 01:01:11
合計ジャッジ時間 3,928 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

"""

import sys
from sys import stdin
import math

def Monotone_Chain(vlis):

    def upstate(a,b,c):
        B = (b[0]-a[0],b[1]-a[1])
        C = (c[0]-a[0],c[1]-a[1])
        return B[1] * C[0] < C[1] * B[0]

    def downstate(a,b,c):
        B = (b[0]-a[0],b[1]-a[1])
        C = (c[0]-a[0],c[1]-a[1])
        return B[1] * C[0] > C[1] * B[0]

    N = len(vlis)
    vc = [vlis[i] for i in range(N)]

    if N >= 3:
        
        vc.sort()

        uv = []

        for v in vc:
            uv.append(v)
            while len(uv) >= 3 and upstate(uv[-3],uv[-2],uv[-1]):
                del uv[-2]

        dv = []
        for v in vc:
            dv.append(v)
            while len(dv) >= 3 and downstate(dv[-3],dv[-2],dv[-1]):
                del dv[-2]


        #print (uv,dv)
        tmp = dv[1:-1]
        tmp.reverse()
        uv += tmp

        return uv

    else:
        return vc

def three_points_on_a_line(a,b,c,d,e,f):

    dx1 = a-c
    dy1 = b-d
    dx2 = a-e
    dy2 = b-f

    return dx2*dy1 == dx1*dy2

def delete_line3(lis):

    ret = []

    for v in lis:

        if len(ret) < 3:
            ret.append(v)
        else:
            x,y = ret[-2],ret[-1]
            if not three_points_on_a_line(x[0],x[1],y[0],y[1],v[0],v[1]):
                ret.append(v)

    return ret

N = 10**6

lis = []

D = 10**9

for i in range(N):

    r = (i * 2*math.pi) / N
    tup = [ int(D * math.cos(r)) , int(D * math.sin(r))  ]

    assert 0 <= abs(tup[0]) <= D
    assert 0 <= abs(tup[1]) <= D

    lis.append(tup)


ans = Monotone_Chain(lis)
ans.reverse()

print (len(ans),file=sys.stderr)

ans = delete_line3(ans)

print (len(ans))
for tup in ans:
    print (tup[0],tup[1])
0