首页 > 代码库 > uva 1549 - Lattice Point(暴力)

uva 1549 - Lattice Point(暴力)

题目链接:uva 1549 - Lattice Point

题目大意:给定圆半径,以原点为圆心,求园内有多少个整数点。

解题思路:首先坐标轴将圆分成4份,所以只要单独考虑每一块的个数乘4再加1即可(原点)

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const double pi = 4 * atan(1.0);
typedef long long ll;

ll solve (ll R) {
    ll ret = 0;

    ll r = R, M = R * R;
    for (ll i = 0; i <= R; i++) {
        while (r * r + i * i > M)
            r--;
        ret += r;
    }
    return 4 * ret + 1;
}

int main () {
    ll n;
    while (scanf("%lld", &n) == 1) {
        printf("%lld\n%lld\n", n, solve(n));
    }
    return 0;
}