Problem:


Problem E: Immortal Jewels

不死の宝石

-->

English text is not available in this practice contest.

ある時ある貴族が，ある貧乏な国のおてんばで勇敢なお姫様に惚れ込み結婚を申し込んだ．お姫様は貴族にある条件を出した．その条件とは「不死の宝石」と呼ばれている宝石を大量に持ってくることであった．不死の宝石は，ある山の特定の場所でしか取ることができない非常に希少な宝石である．しかも大変壊れやすいため，採取するには特別な方法が必要だった．

不死の宝石は円形をしており，二次元空間上に複数存在している．この宝石を取るには，ある特別な金属の棒でそれらを吸着する必要がある．金属の棒は無限の長さを持つ直線であり，太さは無視することができる．宝石は一つ一つ異なる強さの磁力を持っており，金属がその磁力に反応するほど十分に近ければ宝石は吸着される．具体的には，金属と宝石の表面との距離を d ，宝石の磁力の強さを m としたとき，

0 ≤ d ≤ m

であれば宝石は金属に吸着される．逆に，金属の棒と宝石がその磁力よりも離れている場合は吸着できない．また，棒が少しでも宝石を貫通してしまった場合にも，その宝石が壊れてしまうため吸着できない．

例を見てみよう．下の図は二次元空間上に置かれた宝石の例である．宝石1から宝石6まであり，磁力はそれぞれ1, 0, 1, 1, 1, 2であるとする．

図 E-1: 宝石の配置例

上の図に加えて金属の棒を配置した例が下の図である．宝石を吸着した結果も表に示してある．この例の場合，宝石3は磁力の届く範囲より離れており，また宝石4は棒に貫通されているため吸着できないが，残りの4つは全て吸着することができる．

図 E-2: 金属の棒の配置例

	

		宝石名
		磁力
		金属との距離
		吸着できるか
	

	

		宝石1
		1
		約0.21
		できる
	

	

		宝石2
		0
		0
		できる
	

	

		宝石3
		1
		約5.37
		できない
	

	

		宝石4
		1
		貫通している
		できない
	

	

		宝石5
		1
		約0.97
		できる
	

	

		宝石6
		2
		約0.53
		できる
	

表 E-3: 吸着結果

貴族は全財産を注ぎ込み，特別な金属の棒を必死に探し求めた．しかしながら，この金属も非常に貴重であったため，結局たった一本しか入手することができなかった．したがって吸着のチャンスはただ一回しか無い．

あなたはある貴族に仕えるプログラマーである．あなたの仕事は，与えられた二次元上の宝石の配置に対して，金属の棒をうまく配置したときに，最大で何個の宝石を吸着することができるかを求めるプログラムを書くことである．

Input

入力は複数のデータセットから成り， 1つのデータセットは以下の形式で与えられる．

N

x1 y1 r1 m1

x2 y2 r2 m2

...

xN yN rN mN

データセットの最初の行は宝石の数 N (1 ≤ N ≤ 50) を表している．続く N 行の各行には4つの整数 xi, yi, ri, mi (-1000 ≤ xi, yi ≤ 1000, 1 ≤ ri ≤ 100, 0 ≤ mi ≤ 100) が記述されており，宝石の位置，大きさ，および磁力を表す．すなわち，宝石 i は中心を(xi, yi)とし半径が ri であるような円形をしており，その磁力は mi である．宝石は互いに重なり合うことは無い．

入力の終わりは，0のみからなる行で表される．

Output

各データセットについて， 一度に吸着することができる宝石の最大数を1行に出力せよ．

Sample Input

6
-2 -2 1 1
2 2 2 0
5 7 1 1
8 0 3 1
13 4 1 1
16 1 1 2
3
0 0 2 1
10 0 2 1
0 10 2 1
3
0 0 2 1
10 0 2 1
0 6 2 1
3
0 0 2 1
10 0 2 1
0 4 2 1
1
0 0 1 1
0

Output for the Sample Input

4
2
3
3
1



Sample input:
6
-2 -2 1 1
2 2 2 0
5 7 1 1
8 0 3 1
13 4 1 1
16 1 1 2
3
0 0 2 1
10 0 2 1
0 10 2 1
3
0 0 2 1
10 0 2 1
0 6 2 1
3
0 0 2 1
10 0 2 1
0 4 2 1
1
0 0 1 1
0


Sample output:
4
2
3
3
1

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def common_tangent_lines(x1, y1, r1, x2, y2, r2):
    result = []
    xd = x2 - x1; yd = y2 - y1

    rr0 = xd**2 + yd**2
    if (r1 - r2)**2 <= rr0:
        cv = r1 - r2
        if rr0 == (r1 - r2)**2:
            bx = r1*cv*xd/rr0
            by = r1*cv*yd/rr0
            result.append([
                (x1 + bx, y1 + by),
                (x1 - yd + bx, y1 + xd + by),
            ])
        else:
            sv = (rr0 - cv**2)**.5
            px = (cv*xd - sv*yd); py = (sv*xd + cv*yd)
            result.append([
                (x1 + r1*px/rr0, y1 + r1*py/rr0),
                (x2 + r2*px/rr0, y2 + r2*py/rr0),
            ])
            qx = (cv*xd + sv*yd); qy = (-sv*xd + cv*yd)
            result.append([
                (x1 + r1*qx/rr0, y1 + r1*qy/rr0),
                (x2 + r2*qx/rr0, y2 + r2*qy/rr0),
            ])
    if (r1 + r2)**2 <= rr0:
        cv = r1 + r2
        if rr0 == (r1 + r2)**2:
            bx = r1*cv*xd/rr0
            by = r1*cv*yd/rr0
            result.append([
                (x1 + bx, y1 + by),
                (x1 - yd + bx, y1 + xd + by),
            ])
        else:
            sv = (rr0 - cv**2)**.5
            px = (cv*xd - sv*yd); py = (sv*xd + cv*yd)
            result.append([
                (x1 + r1*px/rr0, y1 + r1*py/rr0),
                (x2 - r2*px/rr0, y2 - r2*py/rr0),
            ])
            qx = (cv*xd + sv*yd); qy = (-sv*xd + cv*yd)
            result.append([
                (x1 + r1*qx/rr0, y1 + r1*qy/rr0),
                (x2 - r2*qx/rr0, y2 - r2*qy/rr0),
            ])
    return result

def solve():
    N = int(readline())
    if N == 0:
        return False
    P = [list(map(int, readline().split())) for i in range(N)]
    if N == 1:
        write("1\n")
        return True
    LL = [(r, r+m) for x, y, r, m in P]
    EPS = 1e-9
    ans = 0
    for i in range(N):
        xi, yi, ri, mi = P[i]
        LLi = LL[i]
        for j in range(i):
            xj, yj, rj, mj = P[j]
            LLj = LL[j]
            for pi in LLi:
                for pj in LLj:
                    lines = common_tangent_lines(xi, yi, pi, xj, yj, pj)
                    for p0, p1 in lines:
                        x0, y0 = p0; x1, y1 = p1
                        dx = x1 - x0; dy = y1 - y0
                        q = (dx**2 + dy**2)**.5
                        cnt = 0
                        for xk, yk, rk, mk in P:
                            zx = xk - x0; zy = yk - y0
                            p = abs(dx*zy - dy*zx)
                            if rk*q - EPS <= p <= (rk+mk)*q + EPS:
                                cnt += 1
                        ans = max(ans, cnt)
    write("%d\n" % ans)
    return True
while solve():
    ...