結果
問題 | No.5009 Draw A Convex Polygon |
ユーザー | titia |
提出日時 | 2022-12-02 04:56:38 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,416 bytes |
コンパイル時間 | 341 ms |
実行使用メモリ | 14,920 KB |
スコア | 0 |
最終ジャッジ日時 | 2022-12-02 04:56:47 |
合計ジャッジ時間 | 8,165 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
ソースコード
from math import sqrt M=10**9 ANS=[(0,M)] N=2000000 while len(ANS)<N and ANS[-1][0]<10**9-100: NG=ANS[-1][0]+1000 OK=min(M,NG+100) while OK>NG+1: mid=(OK+NG)//2 y=round(sqrt(M*M-mid*mid)) if y<ANS[-1][1]-100: OK=mid else: NG=mid ANS.append((OK,round(sqrt(M*M-OK*OK)))) #print(len(ANS)) #ANS=ANS[:N] from operator import itemgetter P=ANS P.sort(key=itemgetter(1)) # 一番左下の点から始める。 P.sort(key=itemgetter(0)) # 上側凸包と下側凸包 Q1=[] Q2=[] def outer_product(x,y,z,w): return x*w-y*z for x,y in P: while True: if len(Q1)<2: break s,t=Q1[-1] u,v=Q1[-2] if outer_product(u-s,v-t,x-u,y-v)<0: Q1.pop() else: break Q1.append((x,y)) while True: if len(Q2)<2: break s,t=Q2[-1] u,v=Q2[-2] if outer_product(u-s,v-t,x-u,y-v)>0: Q2.pop() else: break Q2.append((x,y)) Q2.reverse() Q=Q1+Q2[1:] # 上側凸包と下側凸包を結んで凸包が完成 ANS=[] for i in range(len(Q)): x,y=Q[i] z,w=Q[-1-i] ANS.append(str(x)+" "+str(y)) ANS.append(str(-z)+" "+str(w)) ANS.append(str(-x)+" "+str(-y)) ANS.append(str(z)+" "+str(-w)) n=10**6 print(n,flush=True) ANS=ANS[:n] print("\n".join(ANS),flush=True)