結果
問題 | No.5009 Draw A Convex Polygon |
ユーザー | 👑 Kazun |
提出日時 | 2022-12-02 00:21:33 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,048 bytes |
コンパイル時間 | 280 ms |
実行使用メモリ | 105,456 KB |
スコア | 0 |
平均クエリ数 | 14019.00 |
最終ジャッジ日時 | 2022-12-02 00:21:35 |
合計ジャッジ時間 | 2,367 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
ソースコード
#floor(a^(1/k)) を求める. def Floor_Root(a,k): """floor(a^(1/k)) を求める. a:非負整数 k:正の整数 """ assert 0<=a and 0<k if a==0: return 0 if k==1: return a #大体の値を求める. x=int(pow(a,1/k)) #増やす while pow(x+1,k)<=a: x+=1 #減らす while pow(x,k)>a: x-=1 return x #================================================== def check(a,b,c,d,x,y): ux=c-a; uy=d-b vx=x-c; vy=y-d return vx*uy-vy*ux>0 #================================================== def solve(): N=10**6 R=10**6 P=[None]*N; k=0 for x in range(-R,R+1): y=Floor_Root(R*R-x*x,2) if k<=1 or check(*P[k-2], *P[k-1], x, y): P[k]=(x,y) k+=1 if k==N: break return P[:k] #================================================== import sys input=sys.stdin.readline write=sys.stdout.write string=lambda p:"{} {}".format(*p) ans=solve() print(len(ans)) write("\n".join(map(string,ans)))