Counting tiles (Ice Base) - タイルを数える
どんな問題?
Counting tiles
http://www.checkio.org/mission/counting-tiles/
半径Nの円の中に、1x1のタイルがどれだけ含まれるかを求めよ。
(全体が含まれるタイルが何枚、一部が含まれるタイルが何枚あるか。)
円の中心は、4枚のタイルの交差する点となる。
引数は、円の半径で、4以下の浮動小数点が与えられる。
戻り値は、全体が含まれるタイルの数と、一部が含まれるタイルの数をリストで返す。
例題:
checkio(2) == [4, 12] checkio(3) == [16, 20] checkio(2.1) == [4, 20] checkio(2.5) == [12, 20]
どうやって解く?
例題の答えが全て4の倍数であることからも、円の中心を原点として第1象限だけで計算して、最後に4倍すればいいだろう。
タイルの左下の座標をp0、右上の座標をp1とし、
- p0,p1ともに円に含まれていれば、タイルの全体が円の内部にある。
- p0だけが円に含まれていれば、タイルの一部分が円の内部にある。
とわかる。
from itertools import product from math import hypot, ceil def checkio(radius): whole, partial = 0, 0 for x0, y0 in product(range(ceil(radius)), repeat=2): if hypot(x0, y0) < radius: x1, y1 = x0 + 1, y0 + 1 if hypot(x1, y1) <= radius: whole += 4 else: partial += 4 return [whole, partial]
http://www.checkio.org/mission/counting-tiles/publications/natsuki/python-3/first/
点が円周上にある場合をどうするか迷ったが、p0が円周上ならカウントしない。p1が円周上ならタイル全体が含まれる、とした。