ABC389-D Squares in Circle

問題へのリンク

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("2");
            //5
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            //37
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("26");
            //2025
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static decimal mR;
    static decimal mR_Nijyou;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mR = decimal.Parse(InputList[0]);
        mR_Nijyou = mR * mR;

        decimal Answer = 0;
        for (decimal Y = 1; Y < decimal.MaxValue; Y++) {
            if (DeriveNorm(0.5M, 1M, 0.5M, Y) > mR_Nijyou) {
                break;
            }
            decimal MaxX = DeriveMaxX(Y);
            decimal CurrAnswer = (MaxX - 1) * 2 + 1;
            Answer += (MaxX - 1) * 2 + 1;

            if (Y >= 2) {
                Answer += (MaxX - 1) * 2 + 1;
            }
        }
        Console.WriteLine(Answer);
    }

    // Y座標を引数として、X座標の上限を返す
    static decimal DeriveMaxX(decimal pY)
    {
        long L = 1;
        long R = (long)mR + 1;

        while (L + 1 < R) {
            long Mid = (L + R) / 2;
            if (CanAchieve((decimal)Mid, pY)) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }

    // 座標を引数として、NormがR以下かを返す
    static bool CanAchieve(decimal pX, decimal pY)
    {
        decimal Norm = DeriveNorm(0.5M, pX, 0.5M, pY);
        return Norm <= mR_Nijyou;
    }

    // 2点間のNormを返す
    static decimal DeriveNorm(decimal pX1, decimal pX2, decimal pY1, decimal pY2)
    {
        return (pX1 - pX2) * (pX1 - pX2) + (pY1 - pY2) * (pY1 - pY2);
    }
}

解説

Y座標を全探索し、X座標はどこまで伸ばせるかを二分探索してます。
集計は対称性を使ってます。