Problem:


		
Problem C: Dragon Fantasy

		

			永遠に続くと思われていた平和は突然終わりを告げた。 はるか昔に封印されていた魔王がついに復活を遂げたのである。 だが、今まさに世界が闇に覆われようとしているとき、1 人の勇者が現れた。 そしてその勇者は、世界各地に散らばっている伝説のクリスタルを集める旅に出た。 伝説によると、全てのクリスタルを集めることができたならば、どのような願いでもかなえられるという伝説の龍神を呼び出すことができると伝えられている。 その龍神の力を借りれば魔王を倒すことも可能なはずだ。
		

		

			クリスタルは世界各地に散らばっている。 勇者はそれらを 1 つずつ、自らの手で集めていく必要がある。 なぜなら、勇者以外の者がクリスタルを手に入れたならば、魔王の手先によって奪われてしまうかもしれないからである。 勇者は、1 日あたりユークリッド距離で 1 だけ移動することができる。
		

		

			しかし、ここで 1 つの重大な問題がある。 魔王は、常に闇の瘴気をまき散らしており、その瘴気に汚染された場所は人が立ち入ることのできない死の大地と化してしまう。 たとえ勇者であってもその場所に立ち入ることはできない。 さらに、その瘴気は時間とともに同心円状に広まっていくため、 時間の経過とともに勇者の移動できる領域は減少していってしまう。 瘴気は 1 日あたりユークリッド距離 1 だけ広がることが確認されている。 そして、その境界線上にあるクリスタルを勇者は取ることはできない。また、復活したばかりの魔王は力を蓄えるために動かないことも分かっている。
		

		

			勇者は一刻も早くクリスタルを手に入れなければならない。 しかし、もし全てのクリスタルを手に入れることが不可能であるならば、別の手段を考えなければならないだろう。 そこで、あなたには勇者の初期位置と魔王の復活した場所、そしてクリスタルの存在する位置から、全てのクリスタルを手に入れることができるかどうかを調べるプログラムを作っていただきたい。
		

		

			ちなみに、勇者は疲れない。 そして眠らない。 全てのクリスタルを集めて世界を救うまでは絶えず動き続け、クリスタルを集めるのだ！！
		

		
Input

		

			入力は複数のテストケースから構成される。 各テストケースの先頭の行では 5 つの整数 n (0 < n <= 20)、hx 、hy 、dx 、dy が与えられる。
			n はクリスタルの個数、(hx , hy ) は魔王が復活した瞬間での勇者の位置、(dx , dy ) は魔王が復活した位置である。
			後に続く n 行には、各クリスタルの位置を表す 2 つの整数 cx 、cy が与えられる。 入力は n = hx = hy = dx = dy = 0 のときに終了し、これはテストケースには含まない。
		

		

			入力で与えられる全ての座標は絶対値が 1000 以下の整数であることが保証されている。
        

		
Output

			
各テストケースについて、全てのクリスタルを集めることができるならば「YES」と、そうでないならば「NO」と出力せよ。
			

		
Sample Input

		

2 0 0 10 10
1 1
4 4
2 0 0 10 10
1 1
6 6
2 0 0 10 10
1 1
5 5
0 0 0 0 0

		
Output for the Sample Input

		

YES
NO
NO



Sample input:
2 0 0 10 10
1 1
4 4
2 0 0 10 10
1 1
6 6
2 0 0 10 10
1 1
5 5
0 0 0 0 0


Sample output:
YES
NO
NO

Submission status: Wrong Answer

Solution code:
def distance(pos_a,pos_b):
    total = 0
    total += abs(pos_a[0] - pos_b[0])
    total += abs(pos_a[1] - pos_b[1])
    return total

while True:
    crystal = []
    n,yx,yy,mx,my = map(int,raw_input().split())
    if(n == 0 and yx == 0 and yy == 0 and mx == 0 and my == 0):
        break
    for i in xrange(n):
        crystal.append(map(int,raw_input().split()))
    success = True
    for crystal_position in crystal:
        if(distance([mx,my],crystal_position) <= distance([yx,yy],crystal_position)):
            success = False
    if(success == True):
        print "YES"
    else:
        print "NO"

Submission status: Wrong Answer

Solution code:
def distance(pos_a,pos_b):
    total = 0
    total += abs(pos_a[0] - pos_b[0])
    total += abs(pos_a[1] - pos_b[1])
    return total

while True:
    crystal = []
    n,yx,yy,mx,my = map(int,raw_input().split())
    if(n == 0 and yx == 0 and yy == 0 and mx == 0 and my == 0):
        break
    for i in xrange(n):
        crystal.append(map(int,raw_input().split()))
    success = True
    for crystal_position in crystal:
        if(distance([mx,my],crystal_position) < distance([yx,yy],crystal_position)):
            success = False
    if(success == True):
        print "YES"
    else:
        print "NO"

Submission status: Wrong Answer

Solution code:
import sys
import math
EPS = 10**(-10)

def solve(t,x,y,c):
    global ans
    if ans: return

    for i in xrange(len(c)):
        #print sys.stderr, i
        nt = t + math.hypot(c[i][0]-x, c[i][1]-y)
        if math.hypot(dx-c[i][0], dy-c[i][1]) < nt + EPS: return

    for i in xrange(len(c)-1, -1, -1):
        if ans: return
        #print sys.stderr, i,c[i],len(c)
        nt = t + math.hypot(c[i][0]-x, c[i][1]-y)
        c.remove((c[i][0],c[i][1]))
        #print sys.stderr, c
        if c == []:
            ans = True
            return
        solve(nt,x,y,c)

while 1:
    n,hx,hy,dx,dy = map(int, raw_input().split())
    if not(n or hx or hy or dx or dy): break
    c = []
    ans = False
    for i in xrange(n):
        x,y = map(int, raw_input().split())
        c.append((x,y))
    solve(0.0,hx,hy,c)
    if ans: print 'YES'
    else: print 'NO'

Submission status: Accepted

Solution code:
from math import sqrt


def dfs(remains, elapsed, hx, hy, prev):
    global crystals, dc

    if not remains:
        return True

    remains_c = set()
    for i in remains:
        cx, cy, dfd = crystals[i]
        new_elapsed = elapsed + dc[prev][i]
        if dfd <= new_elapsed:
            return False
        remains_c.add((i, cx, cy, new_elapsed))

    for i, cx, cy, new_elapsed in remains_c:
        remains.remove(i)
        if dfs(remains, new_elapsed, cx, cy, i):
            return True
        remains.add(i)

    return False


while True:
    n, hx, hy, dx, dy = map(int, input().split())
    if n == 0: break

    crystals_in = [tuple(map(int, input().split())) for _ in range(n)]
    crystals = [(cx, cy, sqrt((cx - dx) ** 2 + (cy - dy) ** 2)) for cx, cy in crystals_in]
    crystals_in += [(hx, hy)]
    dc = [[sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2) for x2, y2 in crystals_in] for x1, y1 in crystals_in]

    print('YES' if dfs(set(range(n)), 0, hx, hy, n) else 'NO')

Submission status: Accepted

Solution code:
def solve():
    from math import sqrt
    from sys import stdin
    f_i = stdin
    
    def dfs(point, remain, elapsed):
        if not remain:
            return True
        
        next_c = set()
        for c in remain:
            new_elapsed = elapsed + adj[point][c]
            if new_elapsed >= from_d[c]:
                return False
            next_c.add((c, new_elapsed))
        
        for c, new_elapsed in next_c:
            remain.remove(c)
            if dfs(c, remain, new_elapsed):
                return True
            remain.add(c)
        
        return False
    
    while True:
        n, hx, hy, dx, dy = map(int, f_i.readline().split())
        if n == 0:
            break
        
        C = [tuple(map(int, f_i.readline().split())) for i in range(n)]
        from_d = tuple(sqrt((cx - dx) ** 2 + (cy - dy) ** 2) for cx, cy in C)
        C.append((hx, hy))
        adj = tuple(tuple(sqrt((px - qx) ** 2 + (py - qy) ** 2) for qx, qy in C) for px, py in C)
        
        if dfs(n, set(range(n)), 0):
            print("YES")
        else:
            print("NO")

solve()

Submission status: Runtime Error

Solution code:
from math import sqrt


def dfs(remains, elapsed, hx, hy):
    global crystals

    if not remains:
        return True

    remains_c = set()
    for i in remains:
        cx, cy, dfd = crystals[i]
        dfh = sqrt((cx - hx) ** 2 + (cy - hy) ** 2)
        new_elapsed = elapsed + dfh
        if dfd <= new_elapsed:
            return False
        remains_c.add((i, cx, cy, new_elapsed))

    for i, cx, cy, new_elapsed in remains_c:
        remains.discard(i)
        if dfs(remains, new_elapsed, cx, cy):
            return True
        remains.add(i)

    return False


while True:
    n, hx, hy, dx, dy = map(int, input().split())
    if n == 0: break

    crystals = [(cx, cy, sqrt((cx - dx) ** 2 + (cy - dy) ** 2)) for cx, cy in
                (map(int, input().split()) for _ in range(n))]

    print('YES' if dfs(set(range(n)), 0, hx, hy) else 'NO')

Submission status: Runtime Error

Solution code:
from math import sqrt


def dfs(remains, elapsed, hx, hy):
    global crystals

    if not remains:
        return True

    remains_c = set()
    for i in remains:
        cx, cy, dfd = crystals[i]
        new_elapsed = elapsed + sqrt((cx - hx) ** 2 + (cy - hy) ** 2)
        if dfd <= new_elapsed:
            return False
        remains_c.add((i, cx, cy, new_elapsed))

    for i, cx, cy, new_elapsed in remains_c:
        remains.remove(i)
        if dfs(remains, new_elapsed, cx, cy):
            return True
        remains.add(i)

    return False


while True:
    n, hx, hy, dx, dy = map(int, input().split())
    if n == 0: break

    crystals = [(cx, cy, sqrt((cx - dx) ** 2 + (cy - dy) ** 2))
                for cx, cy in (map(int, input().split()) for _ in range(n))]

    print('YES' if dfs(set(range(n)), 0, hx, hy) else 'NO')

Submission status: Runtime Error

Solution code:
import sys
import math
EPS = 10**(-10)

def solve(t,x,y):
    global ans
    global done
    if ans: return

    cnt = 0
    for i in xrange(len(c)):
        if done[i]: cnt += 1

    if cnt is n:
        ans = True
        return
    
    for i in xrange(len(c)):
        if done[i]: continue
        nt = t + math.hypot(c[i][0]-x, c[i][1]-y)
        if math.hypot(dx-c[i][0], dy-c[i][1]) < nt + EPS: return

    for i in xrange(len(c)-1, -1, -1):
        if done[i]: continue
        #print sys.stderr, i,c[i],len(c)
        done[i] = True
        nt = t + math.hypot(c[i][0]-x, c[i][1]-y)
        solve(nt,c[i][0],c[i][1])
        done[i] = False

while 1:
    n,hx,hy,dx,dy = map(int, raw_input().split())
    if not(n or hx or hy or dx or dy): break
    c = []
    ans = False
    for i in xrange(n):
        x,y = map(int, raw_input().split())
        c.append((x,y))
    done = [False for i in xrange(len(c))]
    solve(0.0,hx,hy)
    if ans: print 'YES'
    else: print 'NO'