Submission #2474271


Source Code Expand

N = int(input())
S = []; T = []; R = []
for i in range(N):
    r, sx, sy, tx, ty = map(int, input().split())
    S.append((sx, sy))
    T.append((tx, ty))
    R.append(r)

def dot(s, t, u):
    sx, sy = s
    tx, ty = t
    ux, uy = u
    return (tx - sx)*(ux - sx) + (ty - sy)*(uy - sy)

def cross(s, t, u):
    sx, sy = s
    tx, ty = t
    ux, uy = u
    return (tx - sx)*(uy - sy) - (ux - sx)*(ty - sy)

def dist2(s, t):
    sx, sy = s
    tx, ty = t
    return (sx - tx)**2 + (sy - ty)**2

def check(r, s, t, r0, u):
    if dist2(s, u) <= (r + r0)**2 or dist2(t, u) <= (r + r0)**2:
        return 1
    if not 0 <= dot(s, t, u) <= dist2(s, t):
        return 0
    if not 0 <= dot(t, s, u) <= dist2(s, t):
        return 0
    if not (cross(s, t, u))**2 <= dist2(s, t)*(r + r0)**2:
        return 0
    return 1

memo = {0: 0}
def dfs(state):
    if state in memo:
        return memo[state]
    res = 0
    for i in range(N):
        if (state >> i) & 1 == 0:
            continue
        s = S[i]; t = T[i]; r = R[i]
        for j in range(N):
            if i == j:
                continue
            r0 = R[j]
            if (state >> j) & 1:
                u = S[j]
            else:
                u = T[j]
            if check(r, s, t, r0, u):
                break
        else:
            res = max(res, dfs(state ^ (1 << i)) + 1)
    memo[state] = res
    return res
print(dfs(2**N - 1))

Submission Info

Submission Time
Task G - Coin Slider
User yaketake08
Language PyPy3 (2.4.0)
Score 100
Code Size 1466 Byte
Status AC
Exec Time 578 ms
Memory 56792 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 27
Set Name Test Cases
All 00_sample_00, 00_sample_01, 00_sample_02, 10_random_0, 10_random_1, 10_random_2, 10_random_3, 10_random_4, 10_random_5, 10_random_6, 10_random_7, 10_random_8, 10_random_9, 20_small_r_0, 20_small_r_1, 20_small_r_2, 20_small_r_3, 20_small_r_4, 20_small_r_5, 20_small_r_6, 20_small_r_7, 20_small_r_8, 20_small_r_9, 90_align_0, 91_star_0, 99_max_0, 99_max_1
Case Name Status Exec Time Memory
00_sample_00 AC 165 ms 38256 KB
00_sample_01 AC 170 ms 38256 KB
00_sample_02 AC 168 ms 38256 KB
10_random_0 AC 169 ms 38256 KB
10_random_1 AC 168 ms 38256 KB
10_random_2 AC 166 ms 38256 KB
10_random_3 AC 165 ms 38256 KB
10_random_4 AC 169 ms 38256 KB
10_random_5 AC 167 ms 38256 KB
10_random_6 AC 164 ms 38256 KB
10_random_7 AC 165 ms 38256 KB
10_random_8 AC 165 ms 38256 KB
10_random_9 AC 166 ms 38256 KB
20_small_r_0 AC 203 ms 40940 KB
20_small_r_1 AC 314 ms 50776 KB
20_small_r_2 AC 199 ms 40176 KB
20_small_r_3 AC 207 ms 41580 KB
20_small_r_4 AC 203 ms 41452 KB
20_small_r_5 AC 171 ms 38256 KB
20_small_r_6 AC 233 ms 43120 KB
20_small_r_7 AC 330 ms 49880 KB
20_small_r_8 AC 264 ms 46316 KB
20_small_r_9 AC 171 ms 38256 KB
90_align_0 AC 169 ms 38512 KB
91_star_0 AC 197 ms 41584 KB
99_max_0 AC 524 ms 52056 KB
99_max_1 AC 578 ms 56792 KB