結果
問題 | No.5009 Draw A Convex Polygon |
ユーザー | titia |
提出日時 | 2022-12-02 06:18:54 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 870 bytes |
コンパイル時間 | 110 ms |
実行使用メモリ | 15,024 KB |
スコア | 0 |
最終ジャッジ日時 | 2022-12-02 06:19:01 |
合計ジャッジ時間 | 6,387 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
ソースコード
from math import sqrt M=10**9 ANS=[(101000,999999995),(202000, 999999980)] def outer_product(x,y,z,w): return x*w-y*z N=1000000 while len(ANS)<N//4: s,t=ANS[-1] u,v=ANS[-2] OK=10**9 NG=ANS[-1][0] while OK>NG+1: mid=(OK+NG)//2 x,y=mid,round(sqrt(M*M-mid*mid)) if outer_product(u-s,v-t,x-u,y-v)<0: NG=mid else: OK=mid ANS.append((OK,round(sqrt(M*M-OK*OK)))) Q=ANS ANS=[] for i in range(len(Q)): x,y=Q[i] ANS.append(str(x)+" "+str(y)) for i in range(len(Q)): z,w=Q[-1-i] ANS.append(str(z)+" "+str(-w)) for i in range(len(Q)): x,y=Q[i] ANS.append(str(-x)+" "+str(-y)) for i in range(len(Q)): z,w=Q[-1-i] ANS.append(str(-z)+" "+str(w)) n=10**6 ANS=ANS[:n] ANS.reverse() print(len(ANS),flush=True) print("\n".join(ANS),flush=True)