方針
これは自力で解けたので嬉しかったです。コードはスマートではありませんが。。
出発点・到着点を含む円を半径の昇順でソートしたのですが、この処理はいらなかったですね。
出発点から到着点まで移動する間にまたぐ境界の数は各点のどちらかだけ含む円の数に等しいです。
ソースコード
using System; using System.Collections.Generic; using System.Text; public class CirclesCountry { public int leastBorders(int[] X, int[] Y, int[] R, int x1, int y1, int x2, int y2) { Dictionary<int, int> cOf1 = new Dictionary<int, int>(); Dictionary<int, int> cOf2 = new Dictionary<int, int>(); int n = X.Length; for (int i = 0; i < n; i++) if (isIn(X[i], Y[i], R[i], x1, y1)) cOf1.Add(i, R[i]); for (int i = 0; i < n; i++) if (isIn(X[i], Y[i], R[i], x2, y2)) cOf2.Add(i, R[i]); List<KeyValuePair<int, int>> c1 = new List<KeyValuePair<int, int>>(cOf1); c1.Sort(hikaku); List<KeyValuePair<int, int>> c2 = new List<KeyValuePair<int, int>>(cOf2); c2.Sort(hikaku); int ans = 0; for (int i = 0; i < c1.Count; i++) if (cOf2.ContainsKey(c1[i].Key)) break; else ans++; for (int i = 0; i < c2.Count; i++) if (cOf1.ContainsKey(c2[i].Key)) break; else ans++; return ans; } private bool isIn(int cx, int cy, int r, int px, int py) { return Math.Round(Math.Sqrt(Math.Pow((px - cx), 2) + Math.Pow((py - cy), 2)), 4) < r; } private int hikaku( KeyValuePair<int, int> kvp1, KeyValuePair<int, int> kvp2) { return kvp1.Value - kvp2.Value; } }