CSUOJ 1011 Counting Pixels

Description

Did you know that if you draw a circle that fills the screen on your 1080p high definition display, almost a million pixels are lit? That's a lot of pixels! But do you know exactly how many pixels are lit? Let's find out!

Assume that our display is set on a Cartesian grid where every pixel is a perfect unit square. For example, one pixel occupies the area of a square with corners (0,0) and (1,1). A circle can be drawn by specifying its center in grid coordinates and its radius. On our display, a pixel is lit if any part of it is covered by the circle being drawn; pixels whose edge or corner are just touched by the circle, however, are not lit.

Your job is to compute the exact number of pixels that are lit when a circle with a given position and radius is drawn.

Input

The input consists of several test cases, each on a separate line. Each test case consists of three integers, x,y, and r(1≤x,y,r≤1,000,000), specifying respectively the center (x,y) and radius of the circle drawn. Input is followed by a single line with x = y = r = 0, which should not be processed.

Output

For each test case, output on a single line the number of pixels that are lit when the specified circle is drawn.Assume that the entire circle will fit within the area of the display.

Sample Input

Sample Output

4

88

Hint

思路：一个圆的大小是确定的，那么就将圆心放到原点，此时只需求第一象限的方块个数，然后乘4就行了

一开始最容易想到的是直接算方块左下角到原点的距离算出来，然后判断是否比半径小就ok了

#include<stdio.h>

#include<iostream>

using namespace std;

typedef long long ll;

int main()

{

	ll x, r, y;

	ll dis,num;

	while (~scanf("%lld%lld%lld", &x, &y, &r))

	{

		if (!x&&!y&&!r)

			break;

		ll R = r;

		num = 0;

		for (r; r - 1 >= 0; r--)

		{

			for (ll j = 0; j < R; j++)

			{

				dis = j*j + (r - 1)*(r - 1);

				if (dis <= R*R)

					num++;

				if (dis == R*R&&r - 1 >= 0)

					num--;

			}

		}

		printf("%lld\n", 4 * num);

	}

	return 0;

}

/**********************************************************************

	Problem: 1011

	User: leo6033

	Language: C++

	Result: TLE

**********************************************************************/

很快就敲好了，结果一交，TLE

后来仔细，观察了下，发现直接算对应横坐标的高度然后除一想上取整就ok了。

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<math.h>

using namespace std;

typedef long long ll;

int main()

{

	ll x, r, y;

	ll num;

	while (~scanf("%lld%lld%lld", &x, &y, &r))

	{

		if (!x&&!y&&!r)

			break;

		num = 0;

		for (ll i = 0; i < r; i++)

		{

			num += (ll)ceil(sqrt((double)((r*r) - (i*i))));

		}

		printf("%lld\n", 4 * num);

	}

	return 0;

}

/**********************************************************************

	Problem: 1011

	User: leo6033

	Language: C++

	Result: AC

	Time:120 ms

	Memory:2036 kb

**********************************************************************/

巴特西