#45726: 題目翻譯、思路、解答


cracker04012008@gmail.com (lbc)

School : 國立臺中高級工業職業學校
ID : 280265
IP address : [210.209.160.90]
Last Login :
2025-07-13 21:53:28
f008. 怕累的我,把力氣點滿就對了 -- 經典問題 | From: [182.155.212.132] | Post Date : 2025-04-06 02:51

題目翻譯:求最少使用多少正方形能覆蓋一個 n×n 的方格,使得每條線段都被至少被覆蓋一次,並將這些正方形以(x, y, r)列出,(x,y)是正方形左下角的座標,r是邊長。

-------------------------------------------------------------------------------

n=1, n=2 可以視為例外,直接輸出 "1\n0 0 1"、"3\n0 0 1\n0 0 2\n1 1 1"

n>2 時,為了使用「最少的正方形」完成,畫的正方形必須貼在方格的四個角

畫:

  1. 以右下、左上角 為頂點 r1≧n/2 的最小正方形(r1為邊長)
  2. 以左下、右上角 為頂點 0<r2<n, r2≠n-r1 的正方形(r2為邊長)

共 2(n-1) 個正方形 (也就是他求的m)

-------------------------------------------------------------------------------

解答:python

 
ZeroJudge Forum