2018蓝桥杯A组:方格计数（3种方法）

四、题目：方格计数

如图p1.png所示，在二维平面上有无数个1x1的小方格。
我们以某个小方格的一个顶点为圆心画一个半径为1000的圆。
你能计算出这个圆里有多少个完整的小方格吗？
注意：需要提交的是一个整数，不要填写任何多余内容

---

• 分析思路：
  

1.以原点为圆心,半径为1000，则x轴范围（-1000,1000），y轴范围（-1000,1000）
for(x:-1000~1000)
for(x:-1000~1000)
if(x^2+y ^2<=1000 ^2)
需要注意轴上的点是不能形成方格的（图中橘色的点）
2.可以将圆分成4等分，也就是4个卦限，选择其中一个算方格数，最后乘以4
以第一卦限为例
代码1：

public class Fanggenum {
	public static void main(String[] args) {
   int r=0;
   for(int i=-1000;i<=1000;i++) {
	for(int j=-1000;j<=1000;j++) {
		if(i==0||j==0) continue;
		if(i*i+j*j<=1000*1000)
			r++;
	}
}
System.out.println(r*4);
}
}

代码2：第一卦限

public class Fanggenum {
	public static void main(String[] args) {
		int r=0;
		for(int i=1;i<=1000;i++) {
			for(int j=1;j<=1000;j++) {
				if(i*i+j*j<=1000*1000)
					r++;
			}
		}
		System.out.println(r*4);
		}
	}	

代码3：优化

public class Fanggenum {
	public static void main(String[] args) {
        int N=1000;
		int y=N; //y从有边界开始定义到最大，递减
		int ans=0;
		for(int x=1;x<N;x++) {  //x=1时，对应第一列
			while(x*x+y*y>N*N&&y>0)
				y--;
			ans+=y;
		}
		System.out.println(ans*4);
	}
}