Problem:


風よ、私の梅の香りを届けておくれ！

引っ越しが決まり、この地を去ることになった。この土地自体に未練は無いが、１つだけ気になることがある。それは、庭に植えた梅の木のことだ。私は毎年、この梅が花を咲かすことを楽しみにしていた。ここを離れた後は春の楽しみが１つ減ってしまう。私の梅の香りだけでも風に乗って引っ越し先の家まで届き、春を楽しませてはくれないものか。

日本には春を象徴する３つの花がある。梅・桃・桜の３つだ。引っ越し先には、私の梅以外にも、これらの花の香りが届くだろう。しかし、私の梅の香りだけが届く日数が最も多い家に住みたい。

図のように、花の香りは扇状に広がり、その領域は風の向かう方向と強さによって決まる。扇形は風の向かう方向 w を中心にして対称に広がり、風の強さ a を半径とする領域をもつ。香りが広がる角度 d は花の種類によって決まっているが、風の向かう方向と強さは日によって異なる。ただし、同じ日では、すべての場所で風の向かう方向と強さは同じである。

手元には、私の梅以外の梅・桃・桜の位置と花の種類ごとの香りが広がる角度、引っ越し先の家の候補のデータがある。さらに、数日分の風の向かう方向と強さのデータもある。私の梅以外の梅・桃・桜の木と家の位置は、私の梅の位置を原点とした座標で示されている。

これらのデータを使って、私の梅の香りだけが届く日数の最も多い家を探すためのプログラムを書いてみることとしよう。私は有能なプログラマーなのだから！

入力

入力は複数のデータセットからなる。入力の終わりはゼロ２つの行で示される。各データセットは以下の形式で与えられる。

H R
hx1 hy1
hx2 hy2
:
hxH hyH
U M S du dm ds
ux1 uy1
ux2 uy2
:
uxU uyU
mx1 my1
mx2 my2
:
mxM myM
sx1 sy1
sx2 sy2
:
sxS syS
w1 a1
w2 a2
:
wR aR

各行で与えられる数値は１つの空白で区切られている。

１行目に引っ越し先の家の候補の数 H (1 ≤ H ≤ 100) と風の記録の数 R (1 ≤ R ≤ 100) が与えられる。続くH 行に引っ越し先の家の位置が与えられる。hxi とhyiは i 番目の家の x 座標と y 座標を示す-1000 以上1000 以下の整数である。

続く１行に、私の梅以外の梅の木の数 U と、桃・桜の木の数 M、S、梅・桃・桜の香りが広がる角度du、dm、ds が与えられる。U、M、S の範囲は 0 以上10 以下である。角度の単位は度であり、1 以上180 未満の整数である。

続く U 行に私の梅以外の梅の木の位置、続く M 行に桃の木の位置、続く S 行に桜の木の位置が与えられる。uxi と uyi、mxi と myi、sxi と syi はそれぞれ、i 番目の梅・桃・桜の木の x 座標と y 座標を示す、-1000 以上 1000 以下の整数である。

続く R 行に風の記録が与えられる。wi (0 ≤ wi < 360) と ai(0 < ai ≤ 100) は i 日目の風の向かう方向と強さを表す整数である。風の向かう方向は、x 軸の正の向きから反時計回りに測った角度で表し、単位は度とする。

入力は以下の条件を満たすと考えてよい。

 入力される座標はすべて異なるものとする。

 原点には私の梅以外無い。

 どの花についても、花の香りが届く領域の境界から距離が 0.001 以内には家は無い。

データセットの数は 50 を超えない。

出力

データセットごとに、私の梅の香りだけが届く日数の最も多い全ての家の番号を、小さい順に１行に出力する。家の番号の間は空白１つで区切る。行の終わりには空白文字を出力しない。

ただし、どの家についても、私の梅の花の香りだけが届く日が１日もなければ、NA と出力する。

入力例

6 3
2 1
1 2
5 2
1 3
1 5
-2 3
1 1 1 90 30 45
3 -4
-3 0
2 -2
45 6
90 6
135 6
2 1
1 3
5 2
0 1 1 90 30 45
-3 0
2 -2
45 6
0 0

出力例

5 6
NA



Sample input:
6 3
2 1
1 2
5 2
1 3
1 5
-2 3
1 1 1 90 30 45
3 -4
-3 0
2 -2
45 6
90 6
135 6
2 1
1 3
5 2
0 1 1 90 30 45
-3 0
2 -2
45 6
0 0


Sample output:
5 6
NA

Submission status: Wrong Answer

Solution code:
from math import *
def check(hx,hy,fx,fy,df,w,a):
	d = ((hx-fx)**2 + (hy-fy)**2)**0.5
	if d > a: return False
	theta = acos((hx-fx)/d) + (0 if hy-fy > 0 else pi)
	r,l = (w-df/2.0)*pi/180,(w+df/2.0)*pi/180
	return True if r <= theta <= l or r-2*pi <= theta <= l-2*pi else False

while 1:
	H,R = map(int,raw_input().split())
	if H == 0: break
	hxy = [map(int,raw_input().split()) for i in range(H)]
	U,M,S,du,dm,ds = map(int,raw_input().split())
	dxy = [map(int,raw_input().split())+[du] for i in range(U)]
	mxy = [map(int,raw_input().split())+[dm] for i in range(M)]
	sxy = [map(int,raw_input().split())+[ds] for i in range(S)]
	fxy = dxy+mxy+sxy
	count = [0]*H
	for i in range(R):
		w,a = map(int,raw_input().split())
		for j in range(H):
			hx,hy = hxy[j]
			if not check(hx,hy,0,0,du,w,a):
				continue
			for fx,fy,df in fxy:
				if check(hx,hy,fx,fy,df,w,a):
					break
			else:
				count[j] += 1
	mx = max(count)
	if mx > 0:
		print " ".join(map(str,[i+1 for i in range(H) if count[i] == mx]))
	else:
		print "NA"

Submission status: Wrong Answer

Solution code:
from math import *
def check(hx,hy,fx,fy,df,w,a):
	d = ((hx-fx)**2 + (hy-fy)**2)**0.5
	if d > a: return False
	theta = (acos((hx-fx)/d) if hy-fy >= 0 else 2*pi-acos((hx-fx)/d))
	r,l = (w-df/2.0)*pi/180,(w+df/2.0)*pi/180
	return True if r <= theta <= l or r-2*pi <= theta <= l-2*pi else False

while 1:
	H,R = map(int,raw_input().split())
	if H == 0: break
	hxy = [map(int,raw_input().split()) for i in range(H)]
	U,M,S,du,dm,ds = map(int,raw_input().split())
	dxy = [map(int,raw_input().split())+[du] for i in range(U)]
	mxy = [map(int,raw_input().split())+[dm] for i in range(M)]
	sxy = [map(int,raw_input().split())+[ds] for i in range(S)]
	fxy = dxy+mxy+sxy
	count = [0]*H
	for i in range(R):
		w,a = map(int,raw_input().split())
		for j in range(H):
			hx,hy = hxy[j]
			if not check(hx,hy,0,0,du,w,a):
				continue
			for fx,fy,df in fxy:
				if check(hx,hy,fx,fy,df,w,a):
					break
			else:
				count[j] += 1
	mx = max(count)
	if mx > 0:
		print " ".join(map(str,[i+1 for i in range(H) if count[i] == mx]))
	else:
		print "NA"

Submission status: Wrong Answer

Solution code:
from math import *
def check(hx,hy,fx,fy,df,w,a):
	d = ((hx-fx)**2 + (hy-fy)**2)**0.5
	if d-a > 0.001: return False
	theta = (acos((hx-fx)/d) if hy-fy >= 0 else 2*pi-acos((hx-fx)/d))
	r,l = (w-df/2.0)*pi/180,(w+df/2.0)*pi/180
	return True if r <= theta <= l or r-2*pi <= theta <= l-2*pi else False

while 1:
	H,R = map(int,raw_input().split())
	if H == 0: break
	hxy = [map(int,raw_input().split()) for i in range(H)]
	U,M,S,du,dm,ds = map(int,raw_input().split())
	dxy = [map(int,raw_input().split())+[du] for i in range(U)]
	mxy = [map(int,raw_input().split())+[dm] for i in range(M)]
	sxy = [map(int,raw_input().split())+[ds] for i in range(S)]
	fxy = dxy+mxy+sxy
	count = [0]*H
	for i in range(R):
		w,a = map(int,raw_input().split())
		for j in range(H):
			hx,hy = hxy[j]
			if not check(hx,hy,0,0,du,w,a):
				continue
			for fx,fy,df in fxy:
				if check(hx,hy,fx,fy,df,w,a):
					break
			else:
				count[j] += 1
	mx = max(count)
	if mx > 0:
		print " ".join(map(str,[i+1 for i in range(H) if count[i] == mx]))
	else:
		print "NA"

Submission status: Wrong Answer

Solution code:
from math import *
def check(hx,hy,fx,fy,df,w,a):
	d = ((hx-fx)**2 + (hy-fy)**2)**0.5
	if d-a > -0.001: return False
	theta = (acos((hx-fx)/d) if hy-fy >= 0 else 2*pi-acos((hx-fx)/d))
	r,l = (w-df/2.0)*pi/180,(w+df/2.0)*pi/180
	return True if r <= theta <= l or r-2*pi <= theta <= l-2*pi else False

while 1:
	H,R = map(int,raw_input().split())
	if H == 0: break
	hxy = [map(int,raw_input().split()) for i in range(H)]
	U,M,S,du,dm,ds = map(int,raw_input().split())
	dxy = [map(int,raw_input().split())+[du] for i in range(U)]
	mxy = [map(int,raw_input().split())+[dm] for i in range(M)]
	sxy = [map(int,raw_input().split())+[ds] for i in range(S)]
	fxy = dxy+mxy+sxy
	count = [0]*H
	for i in range(R):
		w,a = map(int,raw_input().split())
		for j in range(H):
			hx,hy = hxy[j]
			if not check(hx,hy,0,0,du,w,a):
				continue
			for fx,fy,df in fxy:
				if check(hx,hy,fx,fy,df,w,a):
					break
			else:
				count[j] += 1
	mx = max(count)
	if mx > 0:
		print " ".join(map(str,[i+1 for i in range(H) if count[i] == mx]))
	else:
		print "NA"

Submission status: Wrong Answer

Solution code:
from math import *
def check(hx,hy,fx,fy,df,w,a):
	d = ((hx-fx)**2 + (hy-fy)**2)**0.5
	if d-a > -0.001: return False
	theta = (acos((hx-fx)/d) if hy-fy >= 0 else 2*pi-acos((hx-fx)/d))
	r,l = (w-df/2.0)*pi/180,(w+df/2.0)*pi/180
	return True if r <= theta <= l else False

while 1:
	H,R = map(int,raw_input().split())
	if H == 0: break
	hxy = [map(int,raw_input().split()) for i in range(H)]
	U,M,S,du,dm,ds = map(int,raw_input().split())
	dxy = [map(int,raw_input().split())+[du] for i in range(U)]
	mxy = [map(int,raw_input().split())+[dm] for i in range(M)]
	sxy = [map(int,raw_input().split())+[ds] for i in range(S)]
	fxy = dxy+mxy+sxy
	count = [0]*H
	for i in range(R):
		w,a = map(int,raw_input().split())
		for j in range(H):
			hx,hy = hxy[j]
			if not check(hx,hy,0,0,du,w,a):
				continue
			for fx,fy,df in fxy:
				if check(hx,hy,fx,fy,df,w,a):
					break
			else:
				count[j] += 1
	mx = max(count)
	if mx > 0:
		print " ".join(map(str,[i+1 for i in range(H) if count[i] == mx]))
	else:
		print "NA"

Submission status: Wrong Answer

Solution code:
from math import *
def check(hx,hy,fx,fy,df,w,a):
	d = ((hx-fx)**2 + (hy-fy)**2)**0.5
	if d-a > -0.001: return False
	theta = (acos((hx-fx)/d) if hy-fy >= 0 else 2*pi-acos((hx-fx)/d))
	r,l = (w-df/2.0)*pi/180,(w+df/2.0)*pi/180
	return True if r < theta < l or r-2*pi < theta < l-2*pi else False

while 1:
	H,R = map(int,raw_input().split())
	if H == 0: break
	hxy = [map(int,raw_input().split()) for i in range(H)]
	U,M,S,du,dm,ds = map(int,raw_input().split())
	dxy = [map(int,raw_input().split())+[du] for i in range(U)]
	mxy = [map(int,raw_input().split())+[dm] for i in range(M)]
	sxy = [map(int,raw_input().split())+[ds] for i in range(S)]
	fxy = dxy+mxy+sxy
	count = [0]*H
	for i in range(R):
		w,a = map(int,raw_input().split())
		for j in range(H):
			hx,hy = hxy[j]
			if not check(hx,hy,0,0,du,w,a):
				continue
			for fx,fy,df in fxy:
				if check(hx,hy,fx,fy,df,w,a):
					break
			else:
				count[j] += 1
	mx = max(count)
	if mx > 0:
		print " ".join(map(str,[i+1 for i in range(H) if count[i] == mx]))
	else:
		print "NA"

Submission status: Wrong Answer

Solution code:
from math import *
eps = 1e-7
def check(hx,hy,fx,fy,df,w,a):
	d = ((hx-fx)**2 + (hy-fy)**2)**0.5
	if d-a > -0.001: return False
	theta = (acos((hx-fx)/d) if hy-fy >= 0 else 2*pi-acos((hx-fx)/d))
	r,l = (w-df/2.0)*pi/180,(w+df/2.0)*pi/180
	return True if r+eps < theta < l-eps or r-2*pi+eps < theta < l-2*pi-eps else False

while 1:
	H,R = map(int,raw_input().split())
	if H == 0: break
	hxy = [map(int,raw_input().split()) for i in range(H)]
	U,M,S,du,dm,ds = map(int,raw_input().split())
	dxy = [map(int,raw_input().split())+[du] for i in range(U)]
	mxy = [map(int,raw_input().split())+[dm] for i in range(M)]
	sxy = [map(int,raw_input().split())+[ds] for i in range(S)]
	fxy = dxy+mxy+sxy
	count = [0]*H
	for i in range(R):
		w,a = map(int,raw_input().split())
		for j in range(H):
			hx,hy = hxy[j]
			if not check(hx,hy,0,0,du,w,a):
				continue
			for fx,fy,df in fxy:
				if check(hx,hy,fx,fy,df,w,a):
					break
			else:
				count[j] += 1
	mx = max(count)
	if mx > 0:
		print " ".join(map(str,[i+1 for i in range(H) if count[i] == mx]))
	else:
		print "NA"

Submission status: Wrong Answer

Solution code:
from math import *
eps = 1e-7
def check(hx,hy,fx,fy,df,w,a):
	d = ((hx-fx)**2 + (hy-fy)**2)**0.5
	if d-a > -0.001: return False
	theta = (acos((hx-fx)/d) if hy-fy >= 0 else 2*pi-acos((hx-fx)/d))
	r,l = (w-df/2.0)*pi/180,(w+df/2.0)*pi/180
	return True if r+eps < theta < l-eps or r-2*pi+eps < theta < l-2*pi-eps else False

while 1:
	H,R = map(int,raw_input().split())
	if H == 0: break
	hxy = [map(int,raw_input().split()) for i in range(H)]
	U,M,S,du,dm,ds = map(int,raw_input().split())
	dxy = [map(int,raw_input().split())+[du] for i in range(U)]
	mxy = [map(int,raw_input().split())+[dm] for i in range(M)]
	sxy = [map(int,raw_input().split())+[ds] for i in range(S)]
	fxy = dxy+mxy+sxy
	count = [0]*H
	for i in range(R):
		w,a = map(int,raw_input().split())
		for j in range(H):
			flag = 0
			hx,hy = hxy[j]
			if not check(hx,hy,0,0,du,w,a):
				continue
			for fx,fy,df in fxy:
				if check(hx,hy,fx,fy,df,w,a):
					flag = 1
					break
			count[j] += 1- flag
	mx = max(count)
	if mx > 0:
		print " ".join(map(str,[i+1 for i in range(H) if count[i] == mx]))
	else:
		print "NA"

Submission status: Wrong Answer

Solution code:
from math import *
eps = 1e-7
def check(hx,hy,fx,fy,df,w,a):
	d = ((hx-fx)**2 + (hy-fy)**2)**0.5
	if d-a > -0.001: return False
	theta = (acos((hx-fx)/d) if hy-fy >= 0 else 2*pi-acos((hx-fx)/d))
	r,l = w-df,w+df
	return True if r+eps < theta < l-eps else False

while 1:
	H,R = map(int,raw_input().split())
	if H == 0: break
	hxy = [map(int,raw_input().split()) for i in range(H)]
	U,M,S,du,dm,ds = map(int,raw_input().split())
	du,dm,ds = du*pi/360,dm*pi/360,ds*pi/360
	dxy = [map(int,raw_input().split())+[du] for i in range(U)]
	mxy = [map(int,raw_input().split())+[dm] for i in range(M)]
	sxy = [map(int,raw_input().split())+[ds] for i in range(S)]
	fxy = dxy+mxy+sxy
	count = [0]*H
	for i in range(R):
		w,a = map(int,raw_input().split())
		w = w*pi/180
		if w > pi: w -= 2*pi
		for j in range(H):
			hx,hy = hxy[j]
			if not check(hx,hy,0,0,du,w,a):
				continue
			for fx,fy,df in fxy:
				if check(hx,hy,fx,fy,df,w,a):
					break
			else:
				count[j] += 1
	mx = max(count)
	if mx > 0:
		print " ".join(map(str,[i+1 for i in range(H) if count[i] == mx]))
	else:
		print "NA"

Submission status: Wrong Answer

Solution code:
from math import *
def check(hx,hy,fx,fy,df,w,a):
	if ((hx-fx)**2 + (hy-fy)**2)**0.5 < a and abs(atan2(hy-fy,hx-fx)-w) < df:
		return True
	else:
		return False

while 1:
	H,R = map(int,raw_input().split())
	if H == 0: break
	hxy = [map(int,raw_input().split()) for i in range(H)]
	U,M,S,du,dm,ds = map(int,raw_input().split())
	du,dm,ds = du*pi/360,dm*pi/360,ds*pi/360
	dxy = [map(int,raw_input().split())+[du] for i in range(U)]
	mxy = [map(int,raw_input().split())+[dm] for i in range(M)]
	sxy = [map(int,raw_input().split())+[ds] for i in range(S)]
	fxy = dxy+mxy+sxy
	count = [0]*H
	for i in range(R):
		w,a = map(int,raw_input().split())
		w = w*pi/180
		if w > pi: w -= 2*pi
		for j in range(H):
			hx,hy = hxy[j]
			if not check(hx,hy,0,0,du,w,a):
				continue
			for fx,fy,df in fxy:
				if check(hx,hy,fx,fy,df,w,a):
					break
			else:
				count[j] += 1
	mx = max(count)
	if mx > 0:
		print " ".join(map(str,[i+1 for i in range(H) if count[i] == mx]))
	else:
		print "NA"

Submission status: Accepted

Solution code:
from math import *
def check(hx,hy,fx,fy,df,w,a):
	if ((hx-fx)**2 + (hy-fy)**2)**0.5 < a and Abs(atan2(hy-fy,hx-fx)-w) < df:
		return True
	else:
		return False

def Abs(e):
	e = abs(e)
	if e > pi: e = 2*pi - e
	return e

while 1:
	H,R = map(int,raw_input().split())
	if H == 0: break
	hxy = [map(int,raw_input().split()) for i in range(H)]
	U,M,S,du,dm,ds = map(int,raw_input().split())
	du,dm,ds = du*pi/360,dm*pi/360,ds*pi/360
	dxy = [map(int,raw_input().split())+[du] for i in range(U)]
	mxy = [map(int,raw_input().split())+[dm] for i in range(M)]
	sxy = [map(int,raw_input().split())+[ds] for i in range(S)]
	fxy = dxy+mxy+sxy
	count = [0]*H
	for i in range(R):
		w,a = map(int,raw_input().split())
		w = w*pi/180
		if w > pi: w -= 2*pi
		for j in range(H):
			hx,hy = hxy[j]
			if not check(hx,hy,0,0,du,w,a):
				continue
			for fx,fy,df in fxy:
				if check(hx,hy,fx,fy,df,w,a):
					break
			else:
				count[j] += 1
	mx = max(count)
	if mx > 0:
		print " ".join(map(str,[i+1 for i in range(H) if count[i] == mx]))
	else:
		print "NA"

Submission status: Accepted

Solution code:
from math import atan2, degrees

def calc(dx, dy, d, w, a):
    if dx**2 + dy**2 > a**2:
        return 0
    t = degrees(atan2(dy, dx))
    for i in range(2):
        if w - d/2 <= t + 360*i <= w + d/2:
            return 1
    return 0

while 1:
    H, R = map(int, input().split())
    if H == R == 0:
        break
    HS = [list(map(int, input().split())) for i in range(H)]
    U, M, S, du, dm, ds = map(int, input().split())
    US = [list(map(int, input().split())) for i in range(U)]
    MS = [list(map(int, input().split())) for i in range(M)]
    SS = [list(map(int, input().split())) for i in range(S)]
    ans = [0]*H
    for k in range(R):
        w, a = map(int, input().split())
        for i, (x, y) in enumerate(HS):
            if not calc(x, y, du, w, a):
                continue
            if (
                    any(calc(x - x0, y - y0, du, w, a) for x0, y0 in US) or
                    any(calc(x - x0, y - y0, dm, w, a) for x0, y0 in MS) or
                    any(calc(x - x0, y - y0, ds, w, a) for x0, y0 in SS)
                ):
                continue
            ans[i] += 1
    m = max(ans)
    if m:
        res = [i+1 for i in range(H) if m == ans[i]]
        print(*res)
    else:
        print("NA")