Custom Painting Master

Time Limit : 1 sec, Memory Limit : 65536 KB

Problem I: カスタムペイント職人

slipはとあるレーシングゲームの動画が好きである。 といっても、車が走っている動画が好きであるわけではなく、このゲームに搭載されたカスタムペイントカー作成という機能によって、車体をカスタマイズする動画が好きなのである。 これは、円や多角形などといった基本的な幾何学図形を重ねあわせることで、車体にカスタムペイントができる機能である。

このカスタムペイントによって様々なアートを創りだす、いわゆる職人と呼ばれる人々がいる。 職人達の手にかかれば、車体にガリガリしたアイスキャンディーのキャラクターや、アイドルをプロデュースして楽しむゲームのキャラクターを創りだすことなど造作もない事である。 職人の車は、オークションで高値で取引をされるほどである。

その中でも、slipがお気に入りの職人がいる。 その職人は、扇形の図形のみで様々なアートを創り出している。 その職人は扇形を何枚も重ねあわせることで、自由自在に形を創り出している。

ある日slipは、職人が作るアートにおいて、扇形が一番多く重なっている部分で何枚あるのか気になりだした。 そこで、手作業で数えようと思ったのだが、枚数が多かったために諦めてしまった。

そこで、勝手に友人と思っているあなたに、プログラムを作ってもらうことにした。 あなたの仕事は、与えられた扇形の位置情報から、最大何枚の重なりがあるのか調べることである。 ここでは、扇形同士が接している場合も重なっているものとする。

Input

データセットの入力は以下の形式である。

n
m1
x1 y1 r1 s1 t1
x2 y2 r2 s2 t2
...
xi yi ri si ti
...
xm1 ym1 rm1 sm1 tm1
...
mi
x1 y1 r1 s1 t1
x2 y2 r2 s2 t2
...
xmi ymi rmi smi tmi
mt
...
xmt ymt rmt smt tmt

n(0 < n ≤ 50)はテストケースの個数、 mi(0 < mi ≤ 16)は貼られている扇形の枚数、 xi(0 ≤ xi ≤ 500)は扇形の頂点のx座標、 yi(0 ≤ yi ≤ 500)は扇形の頂点のy座標、 ri(0 < ri ≤ 100)は扇形の半径、 si(0 ≤ si < 360)は扇形の中心角の開始角度(degree)、 ti(0 ≤ ti < 360)は扇形の中心角の終了角度(degree) を表す。

またすべて整数である。 ここで与えられる扇形は必ずしもs < tとは限らない。 s < ts > tの場合の図をそれぞれ図1,2に表す。

図1
図2

ただし入力には図3のように、線と線がぴったりに重なる入力は無いものとする。

図3

Output

各データセットに対し、扇形が重なっている部分の最大枚数を表示せよ。

Sample Input

3
3
17 12 7 340 180
26 22 10 150 270
27 13 5 100 230
3
0 0 8 0 90
10 10 8 180 0
50 50 5 180 270
2
10 10 5 0 270
0 0 30 0 90

Output for Sample Input

3
2
2

Hint

ここでサンプルの1つ目は図4のように配置されている

図4

Source: Ritsumeikan University Programming Contest 2011 , Japan, 2011-10-05