圆上取点（例题）

Protecting The Earth

（圆内取点） 

题目描述：

给定 K (地球上的人数)，你必须制作一个保护罩来保护他们。(地球上的人数），你必须制作一个保护罩来保护他们。

已知一个人只能站在整数的坐标上，并且两个人不能站在同一个地方，求以 (0,0) 坐标为圆心，能容纳 K 人的圆的最小个整数半径。

 输入样例：

3

2

6

13

输出样例： 

1

2

2 

AC代码 

# include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
    int n;
    cin >> n;
    int l = 0, r = n;
    auto check = [&](int x)->bool
    {
        int cnt = 0;
        int my = x;
        for (int i = 1; i<=x; i++){
            while (i*i+my*my > x*x){
                my--;
            }
            cnt += my+1;
        }
        return 4*cnt+1 >= n;
    };
    while (l+1 < r){
        int mid = (l+r)/2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    cout << r << endl;
}
signed main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

圆上的整点

（圆周取点） 

 求一个给定的圆，在圆周上有多少个点的坐标是整数。

输入格式 

输出格式

整点个数

 AC代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long int
#define eps 1e-9
#define REP(i,n) for (int i = 1; i <= (n); i++)
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 1000000000;
LL n,ans = 0;
inline int gcd(int a,int b){return !b ? a : gcd(b,a % b);}
void check(LL d){
	LL R = 2 * n / d,E = (LL)sqrt(R),v;
	for (int i = 1; i < E; i++){
		v = (LL)sqrt(R - i * i);
		if (gcd(i,v) == 1 && i <= v &&i * i + v * v == R) ans++;
	}
}
int main()
{
	cin >> n;
	LL E = (LL)sqrt(2.0 * n);
	for (int i = 1; i <= E; i++){
		if (2 * n % i) continue;
		if (i * i == 2 * n) check(i);
		else check(i),check(2 * n / i);
	}
	cout<<4 * ans + 4<<endl;
	return 0;
}