#42322: O(1) 公式解的證明過程


sam851015@gmail.com (多挖鼻孔有益身心健康)

學校 : 不指定學校
編號 : 277705
來源 : [123.192.228.253]
最後登入時間 :
2024-11-09 20:16:56
d575. 末日審判 -- jack1 | From: [123.192.228.253] | 發表日期 : 2024-09-29 17:39

直接說結論: 任意等腰直角三角形,三角形內任意點P到兩條底邊的距離和一定小於底邊的長度

 

下面的圖形我都是用 GroGebra 畫的(連結)

如果把天譴中心視為原點,並把圖形放到座標平面上,可以看到範圍是長這樣子的
(範圍=5)

 

如果我們只看其中一個象限...

就會變成一個等腰直角三角形,三個頂點分別為 ABO,且 O 為直角

在三角形ABO內任意位置標上 P ,表示首都的位置(在天譴範圍內)

把輔助線畫一畫......
我順便把格子去掉了,懂意思就好

PC 垂直於 OA,PD 垂直於 OB

計算三角形面積公式,可得不等式:

 

其中 OA = OB,化簡到最後就是:

 

註: 當 P 在線段AB上時,PC+PD=OA

這就是證明的完整過程

 

現在回頭看第一張圖

如果我們把中心點不當成原點(0, 0)了,而是當成天譴的中心點

只需要計算首都與兩條對稱軸的距離,與天譴距離的關係,就可以判斷首都是否會被波及

 

 

 
#42324: Re: O(1) 公式解的證明過程


sam851015@gmail.com (多挖鼻孔有益身心健康)

學校 : 不指定學校
編號 : 277705
來源 : [123.192.228.253]
最後登入時間 :
2024-11-09 20:16:56
d575. 末日審判 -- jack1 | From: [123.192.228.253] | 發表日期 : 2024-09-29 18:08

提醒一下 python 如果要用公式解的話,最後一筆測資很可怕,記得用 I/O 輸入、輸出
我直接用 print() 會吃 TLE......

 

用法是導入 sys 的 stdin 和 stdout,分別代表輸入和輸出

 

stdin 在讀取資料可以用

  • stdin.readline - 讀取一行,到換行符 \n 為止,和 input() 的行為相似
  • next(stdin) - 讀取一行,到換行符 \n 為止,和 input() 的行為相似
  • stdinfor 循環,如: for line in stdin: ,效果和上面一樣,但是會不斷讀取到 EOF 為止

需要注意用 stdin 時不會忽略換行符 \n ,所以要記得 rstrip() 處理掉

 

stdout 主要就用 stdout.write()

括號裡面只能放字串,且不會自動換行,所以你要自己處理一下格式,例如:

stdout.write(f"answer\n")

 

麻煩歸麻煩,但效率會高一些,底層原理是用記憶體空間換執行效率,當輸出的資料比較多時, stdout.write() 會比 print() 占用比較多的記憶體空間

 
ZeroJudge Forum