ABC191-D Circle Lattice Points

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("0.2 0.8 1.1");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("100 100 1");
            //5
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("42782.4720 31949.0192 99999.99");
            //31415920098
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        decimal[] wkArr = InputList[0].Split(' ').Select(pX => decimal.Parse(pX)).ToArray();
        decimal X = wkArr[0];
        decimal Y = wkArr[1];
        decimal R = wkArr[2];

        decimal StaX = Math.Truncate(X - R);
        decimal EndX = Math.Truncate(X + R);

        decimal Answer = 0;
        for (decimal LoopX = StaX; LoopX <= EndX; LoopX++) {
            // 円の中心からのX座標の距離
            decimal XLen = Math.Abs(LoopX - X);
            decimal R2 = R * R;
            decimal XLen2 = XLen * XLen;

            double YLenDouble = Math.Sqrt((double)R2 - (double)XLen2);
            decimal YLenDecimal = 0;
            if (double.IsNaN(YLenDouble) == false) {
                YLenDecimal = (decimal)YLenDouble;
            }

            // Y座標の真の値候補
            var YPosKouhoList = new List<decimal>();

            // Y座標は近似値なので前後の値が真の値候補になる
            decimal YPos1 = Math.Truncate(Y + YLenDecimal);
            decimal YPos2 = Math.Truncate(Y - YLenDecimal);
            YPosKouhoList.Add(YPos1 - 1);
            YPosKouhoList.Add(YPos1);
            YPosKouhoList.Add(YPos1 + 1);
            YPosKouhoList.Add(YPos2 - 1);
            YPosKouhoList.Add(YPos2);
            YPosKouhoList.Add(YPos2 + 1);

            // 真の値候補で、円の不等式を満たさないものをRemove
            for (int I = YPosKouhoList.Count - 1; 0 <= I; I--) {
                decimal KouhoYLen = Math.Abs(YPosKouhoList[I] - Y);
                if (XLen * XLen + KouhoYLen * KouhoYLen <= R * R) {
                    continue;
                }
                YPosKouhoList.RemoveAt(I);
            }
            if (YPosKouhoList.Count == 0) continue;

            decimal YPosMax = YPosKouhoList.Max();
            decimal YPosMin = YPosKouhoList.Min();
            //Console.WriteLine("X座標={0}でのY座標は{1}から{2}まで", LoopX, YPosMax, YPosMin);
            Answer += Math.Abs(YPosMax - YPosMin) + 1;
        }
        Console.WriteLine(Answer);
    }
}

解説

円の左端から右端までのX座標を全探索します。
X座標に対応した円周上のY座標は、三平方の定理で求まりますが、
これは誤差がありうる近似値になります。

なので近似値の前後に1移動したY座標を
真のY座標の候補として、

円の内部であることの必要十分条件である不等式
X*X + Y*Y <= R*R
を満たすかをチェックしてます。