Tag Discussion Solution Statistics Submit
 

RUPC 2013 (UAPC)

Balloon Contest

Time Limit : 8 sec, Memory Limit : 65536 KB

Problem F: Ballon Contest

Problem

空の様子がいつもと違う。色とりどりの多彩な熱気球が空を覆っていた。今日は熱気球の大会だ。大会の会場に行ってみると、熱気球を使ったレクリエーションが開催されていた。熱気球から落とされた得点付きボールを参加者全員で取り合うらしい。残念ながら申し込み期限が切れてしまっていたが、せっかくなので優勝者を予想してみることにした。

  • レクリエーションにはN人参加する。
  • N 人の参加者はそれぞれ自分の位置が与えられる。複数の参加者に同じ位置が与えられる事はない。
  • 上空の熱気球からM個のボールが1個ずつ落下する。
  • 参加者は全員同じタイミングで走り始め、ボールに向かって同じ速度で一直線に走る。
  • ボールの落下位置に一番早く辿り着けた人がボールを取得できる。同時に複数人辿り着いた場合は、一様な確率で取得できる人が決まる。
  • 参加者がボールを取得すると参加者全員が元の位置に戻る。
  • 参加者が走り始めてから参加者の全員が元の位置に戻るまでに別のボールが落下する事はない。
  • 各ボールには得点と落下する位置が与えられ、ボールを取得すると得点を得られる。
  • ボールは落下中に空気抵抗を受けるため、実際に落下する地点にはズレが発生する。落下予定の位置より最大でX軸方向に±dx 、Y軸方向に±dy だけ一様な確率でズレる。

得られる得点の期待値を求め、期待値の最も大きい参加者の期待値を出力せよ。

Input

入力は複数のデータセットからなる。
各データセットは以下で表される。

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つのゼロからなる。

Constraints

入力は以下の条件を満たす。

  • 1 ≤ N ≤ 100
  • 1 ≤ M ≤ 10
  • 0 ≤ xi , yi , bxj , byj ≤ 10000
  • 1 ≤ dxj , dyj≤ 10000
  • 1 ≤ scorej ≤ 100
  • テストケースの数は 10 を超えない。
  • 入力に含まれる値は全て整数である。

Output

各データセット毎に、答えを一行に出力しなさい。
出力は0.0001以下の誤差を含んでもよい。

Sample Input

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

Sample Output

5.442857
0.750000
1.000000

Source: Ritsumeikan University Competitive Programming Camp 2013, Day1 , Problem set from University of Aizu teams, Shiga, Japan, 2013-03-11