Kattis discdistrict 有什麼好做法？ | 中學資訊討論群 CISC | Page 1

pale wedge Jan 13, 2023, 11:30 AM

#

大意是給一個以原點 (0, 0) 為圓心、半徑為 r 的圓
求圓外（與圓心距離嚴格 > r）最靠近的格子點（x, y 皆為整數）座標
多組解時任一皆可

目前想到的做法複雜度 O(r) 也已確認 AC
想問問看是不是有比較漂亮的做法或數學解

sage falcon Jan 14, 2023, 2:23 AM

#

感覺(r,1)一定是對的欸

#

因為這樣距離是sqrt(r^2+1)

#

然後又要格子點

#

所以sqrt(r^2+1)應該是最小的

thin hearth Jan 14, 2023, 2:25 AM

#

r 是正整數嗎

#

如果不是 (r,1) 不一定是最佳解

sage falcon Jan 14, 2023, 2:26 AM

#

喔對

#

我以為他是正整數

thin hearth Jan 14, 2023, 2:27 AM

#

他沒說

thin hearth Jan 14, 2023, 3:01 AM

#

我剛剛去看了題目

#

r 是正整數

#

所以答案一定是 (r,1)

#

但我還蠻想知道 r 不是正整數時有沒有比 O(r) 還快的解

#Kattis discdistrict 有什麼好做法？