【经典问题】优雅的点

题目

小易有一个圆心在坐标原点的圆，小易知道圆的半径的平方。小易认为在圆上的点而且横纵坐标都是整数的点是优雅的，小易现在想寻找一个算法计算出优雅的点的个数，请你来帮帮他。例如：半径的平方如果为25优雅的点就有：(+/-3, +/-4), (+/-4, +/-3), (0, +/-5) (+/-5, 0)，一共12个点。

输入描述与输出描述

输入为一个整数，即为圆半径的平方,范围在32位int范围内。 输出为一个整数，即为优雅的点的个数

示例输入与输出

输入25 输出12

代码

#include <stdio.h>
#include <math.h>

int main(void)
{
	int R, r, x, flag = 0, count = 0;
	
	printf("请输入圆半径的平方数：");
	scanf("%d",&R);
	r = (int)sqrt(R);	// 强制转化为整形
	/* 判断一个双精度浮点型数据的整数部分是否与其小数部分相等 */
	if (r == sqrt(R))   
	{
		flag = 1;	// 标记横、纵坐标有0的情况
		r -= 1;
	}
	for ( x = 1; x <= r; x++ )	//坐标没有0的情况：(+/-3, +/-4), (+/-4, +/-3)
	{
		double y = sqrt( R - x*x );
		int y1 = (int)y;
		if ( y1 == y )	
		{
			count++;
		}
	}
	count *= 4;
	if( 1 == flag )	  //坐标有0的情况：(0, +/-5) (+/-5, 0)
	{
		count += 4;
	}	
	
	printf("半径的平方为%d的圆的优雅点的个数为：%d\n", R, count);
	
	return 0;
}

分析

（1）找出 (0, +/-5) (+/-5, 0)这种情况； （2）找出(+/-3, +/-4), (+/-4, +/-3)这种情况。

首先，判断半径平方的算术平方根是否等于其整数部分，如果等于，则存在 (0, +/-5) (+/-5, 0)这种情况，使用flag变量标记下来；对于(+/-3, +/-4), (+/-4, +/-3)这类情况使用勾股定理进行判断验证，以x为自变量，循环遍历至r-1,求逐一对应的y的值，同样判断其算术平方根是否等于其整数部分，如果等于，则存在(+/-3, +/-4), (+/-4, +/-3)这一类情况。最后，算出两类情况的优雅的点的总数。

运行结果

---