読者です 読者をやめる 読者になる 読者になる

日々精進

新しく学んだことを書き留めていきます

SRM443 Div2 Mid

IT TopCoder

方針
これは自力で解けたので嬉しかったです。コードはスマートではありませんが。。
出発点・到着点を含む円を半径の昇順でソートしたのですが、この処理はいらなかったですね。
出発点から到着点まで移動する間にまたぐ境界の数は各点のどちらかだけ含む円の数に等しいです。
ソースコード

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;
    }
}