競プロ初中級者100問

square869120Contest#5B - Emblem

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/s8pc-5/tasks/s8pc_5_b

方針

  • 半径が決まっていないM個の円同士の関係に着目する。この時、最も小さい円の半径の最大値は最も近い二点間の距離の半分であることが分かる。
  • 半径が決まっているN個の円とM個の円の関係に着目する。この時、最も小さい円の半径の最大値は二点間の距離から半径が決まっている円の半径を引いた値を全ての組み合わせについて調べ、その最小値となることが分かる。
    以上の二つの値のうち、小さい値が解となる。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from itertools import combinations
INF = 10**10
ans = INF # 最小値を更新するのでINFで初期化
N, M = map(int,input().split())
c_n = []
c_m = []
for n in range(N):
    c_n.append(list(map(int,input().split())))
for m in range(M):
    c_m.append(list(map(int,input().split())))

def dist(c1,c2): # ユークリッド距離を返却する
    return pow(((c1[0]-c2[0])**2 + (c1[1]-c2[1])**2),0.5)

for c1,c2 in combinations(c_m,2): # M個の円同士
    ans = min(ans,dist(c1,c2)/2) # 二点間の距離の半分

for c1 in c_n: # N個の円とM個の円
    ans = min(ans,c1[2]) # 半径が決まっている円もチェック対象
    for c2 in c_m:
        ans = min(dist(c1[:2],c2) - c1[2], ans) # 二点間の距離から半径が決まっている円の半径を引く
print (ans)

記事情報

  • 投稿日：2020年5月14日
  • 最終更新日：2020年5月14日