空の様子がいつもと違う。色とりどりの多彩な熱気球が空を覆っていた。今日は熱気球の大会だ。熱気球から落とされた得点付きボールを参加者全員で取り合うらしい。せっかくなので優勝者を予想してみることにした。
得られる得点の期待値を求め、期待値の最も大きい参加者の期待値を出力せよ。
入力は複数のデータセットからなる。
各データセットは以下で表される。
N M x1 y1 . . xN yN bx1 by1 dx1 dy1 score1 . . bxM byM dxM dyM scoreM
1行目には、参加者の人数 N 、ボールの数 M が与えられる。
2行目から N +1行目までには、参加者の情報が与えられる。 xi , yi は、それぞれ参加者の位置のX座標・Y座標である。
N +2行目から N + M +1行目までには、ボールの情報が与えられる。各ボールが実際に落下する地点のX座標・Y座標はそれぞれ bxj - dxj から bxj + dxj まで、 byj - dyj から byj + dyj までの範囲のどこかである。 scorej はボールの得点である。
入力の終わりは2つのゼロからなる。
入力は以下の条件を満たす。
各データセット毎に、答えを一行に出力しなさい。
出力は0.0001以下の誤差を含んでもよい。
3 4 10 75 50 5 90 75 50 50 10 10 2 40 90 1 1 3 10 20 10 15 1 50 70 50 50 4 4 2 25 25 25 75 75 75 75 25 50 50 10 10 1 50 50 15 15 2 1 1 5 5 1 1 1 1 1 0 0
5.442857 0.750000 1.000000