【1】保护大地球 题目链接
地球是一个坐标平面，您的任务是保护它。 google earth 给定 K (地球上的人数），你必须制作一个保护罩来保护他们。 求以坐标 (0, 0) 为圆心的圆，且能容纳 K 个人的最小的圆的半径。已知一个人只能站在整数坐标上，且 两个人不能站在同一位置。 注 1：一个人可以站在圆的中心。 注 2：如果一个人站在圆环内或圆环的边界，他将被视为受到保护。
Input 唯一一行包含一个整数 K(2 ≤ K ≤ 109 ) - 地球上的人口数量。 Output 打印一个整数：保护地球上 K 个人所需的最小整数圆半径。
1 // 2 //#pragma GCC optimize("Ofast") 3 //#pragma GCC optimize("unroll-loops") 4 #define _CRT_SECURE_NO_WARNINGS 5 #define All(a) a.begin(),a.end() 6 #define INF 2147483647 7 #include<bits/stdc++.h> 8 #include<numeric> 9 using namespace std; 10 typedef unsigned long long ull; 11 #define int long long//再也不用担心开longlong了>< 12 typedef pair<int, int>PII; 13 int n; 14 bool f(int x) { 15 int res = 0; 16 for (int i = 0; i < x; i++) { 17 res += floor(sqrt(x * x - i * i)); 18 } 19 return res * 4 + 1 >= n; 20 } 21 int find() { 22 int l = -1, r = 1e7 + 1; 23 while (l + 1 < r) { 24 int mid =(r-l)/2+l; 25 if (f(mid))r = mid; 26 else l = mid; 27 } 28 return r; 29 } 30 signed main() { 31 ios::sync_with_stdio(false); 32 cin.tie(nullptr); 33 cout.tie(nullptr); 34 cin >> n; 35 cout << find(); 36 }
总结：计算一个圆内整数点个数方法：利用x==y(正方形)，下取整(妙)，以及反求法，复杂度O(N)
1 int cal(int u) { 2 int res = 0; 3 for (int i = 0; i < u; i++) { 4 res += floor(sqrt(u * u - i * i)); 5 } 6 return res*4+1; 7 }