D - Squares in Circle
Source: atcoder
Difficulty: 400

Problem Statement
On the two-dimensional coordinate plane, there is an infinite tiling of
1 \times 1
squares.
Consider drawing a circle of radius
R
centered at the center of one of these squares. How many of these squares are completely contained inside the circle?
More precisely, find the number of integer pairs
(i,j)
such that all four points
(i+0.5,j+0.5)
,
(i+0.5,j-0.5)
,
(i-0.5,j+0.5)
, and
(i-0.5,j-0.5)
are at a distance of at most
R
from the origin.
Constraints
1 \leq R \leq 10^{6}
All input values are integers.
Input
The input is given from Standard Input in the following format:
R
Output
Print the answer.
Sample Input 1
2
Sample Output 1
5
There are a total of five squares completely contained in the circle: the square whose center matches the circle’s center, plus the four squares adjacent to it.
Sample Input 2
4
Sample Output 2
37
Sample Input 3
26
Sample Output 3
2025

C++ solution:
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define ll long long
#define ld long double
#define pb push_back
#define all(v) v.begin(),v.end()
#define MOD 1000000007
#define INF 1000000000000000000
int main(){
    int r;
    cin>>r;
    auto check=[&](int x,int y){
        x=x*2+1;
        y=y*2+1;
        return x*x+y*y <= r*r*4;
    };
    ll x=0;
    ll ans=0;
    for(ll y=r;y>=0;y--){
        while(check(x+1,y)) x++;
        ans+=x;
    }
    cout<<ans*4+1<<endl;
    return 0;
}
//TLEから抜け出せなかった。give up
//解法を見ると、y座標を固定して、x座標を動かしていって、円の外になるまで動かす。尺取り法で実装する。

Go solution:
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
)

var reader *bufio.Reader = bufio.NewReader(os.Stdin)
var writer *bufio.Writer = bufio.NewWriter(os.Stdout)

func printf(f string, a ...interface{}) { fmt.Fprintf(writer, f, a...) }
func scanf(f string, a ...interface{})  { fmt.Fscanf(reader, f, a...) }

func main() {
	defer writer.Flush()

	var r float64
	scanf("%v\n", &r)

	res := 0
	// x^2+y^2 <= r^2
	// x^2+y^2 == r^2
	// y^2 = r^2 - x^2
	for i := 0.0; i <= r; i++ {
		// fmt.Println("x=", i, "の時のy=", math.Sqrt((r*r)-((i+0.5)*(i+0.5)))+0.5)
		res += int(math.Sqrt((r*r)-((i+0.5)*(i+0.5))) + 0.5)
		// for j := 0.0; j < r; j++ {
		// 	if j+0.5 == math.Sqrt(r*r/(i+0.5)*(i+0.5)) {
		// 		res++
		// 	}
		// }
	}
	res -= int(r)

	printf("%d\n", res*4+1)
}

Java solution:
import java.util.*;
import java.io.*;
public class Main {
    public static boolean check(long x, long y, long R) {
        long left = 2*x*x + 2*x + 2*y*y+2*y+1;
        long right = 2*R*R;
        if (left <= right) {
            return true;
        }
        return false;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int R = Integer.parseInt(br.readLine());
        long ans = 0;
        int pointer = R-1;
        for (int i = 1; i < R; i++) {
            while (!check(pointer, i, R)) {
                pointer--;
            }
            ans += pointer;
        }
        System.out.println(4*ans+4*R-3);
    }
}

JavaScript solution:
R=+require('fs').readFileSync(0);
S=0;G=4*(R**2);T=R-1;
for(i=1;i<R;i++){
  K=(2*i+1)**2;
  j=T;
  while(K+((2*j+1)**2)>G)j--;
  S+=j+1;
  T=j+1;
}
console.log(S*4+1);

Python solution:
r=int(input())
ans=4*(r-1)+1
j=int(r-1)
count=0
for i in range(1,r):
    while j>=0:
        inbox=(2*i+1)*(2*i+1)+(2*j+1)*(2*j+1)<=4*r*r
        if inbox:
            count+=j
            break
        else:
            j-=1

ans+=count*4
print(ans)

Ruby solution:
r = gets.to_i

@r2 = r.pow(2)
def count(x)
  (Math.sqrt(@r2 - (x + 0.5) ** 2) - 0.5).to_i
end
c = count(0)
(1...r).each do |x|
  c += count(x)
end
puts c * 4 + 1