2017 ACM-ICPC 亚洲区（南宁赛区）网络赛 G. Finding the Radius for an Inserted Circle(计算几何，二分)
Finding the Radius for an Inserted Circle
Three circles Ca, Cb, and Cc, all with radius R and tangent to each other, are located in two-dimensional space as shown in Figure 1. A smaller circle C1 with radius R1 (R1<R) is then inserted into the blank area bounded by Ca, Cb, and Cc so that C1 is tangent to the three outer circles, Ca, Cb, and Cc. Now, we keep inserting a number of smaller and smaller circles Ck (2≤k≤N) with the corresponding radius Rk into the blank area bounded by Ca, Cc and Ck−1 (2≤k≤N), so that every time when the insertion occurs, the inserted circle Ck is always tangent to the three outer circles Ca, Cc and Ck−1, as shown in Figure 1
Figure 1.
(Left) Inserting a smaller circle C1 into a blank area bounded by the circle Ca, Cb and Cc.
(Right) An enlarged view of inserting a smaller and smaller circle Ck into a blank area bounded by Ca, Cc and Ck−1 (2≤k≤N), so that the inserted circle Ck is always tangent to the three outer circles, Ca, Cc, and Ck−1.
Now, given the parameters R and k, please write a program to calculate the value of Rk, i.e., the radius of the k−th inserted circle. Please note that since the value of Rk may not be an integer, you only need to report theinteger part of Rk. For example, if you find that Rk = 1259.8998 for some k, then the answer you should report is 1259.
Another example, if Rk = 39.1029 for some k, then the answer you should report is 39.
Assume that the total number of the inserted circles is no more than 10, i.e., N≤10. Furthermore, you may assume π=3.14159. The range of each parameter is as below:
1≤k≤N, and 104≤R≤107.
Input Format
Contains l+3 lines.
Line 1: l ----------------- the number of test cases, l is an integer.
Line 2: R ---------------- R is a an integer followed by a decimal point,then followed by a digit.
Line 3: k ---------------- test case #1, k is an integer.
…
Line i+2: k ----------------- test case # i.
…
Line l+2: k ------------ test case #l.
Line l+3: −1 ---------- a constant −1 representing the end of the input file.
Output Format
Contains l lines.
Line 1: k Rk ----------------output for the value of k and Rk at the test case #1, each of which should be separated by a blank.
…
Line i: k Rk ----------------output for k and the value of Rk at the test case # i, each of which should be separated by a blank.
Line l: k Rk ----------------output for k and the value ofRk at the test case # l, each of which should be separated by a blank.
样例输入
1 152973.6 1 -1
样例输出
1 23665
思路：我们可以把三个圆的圆心两两相连，连成一个三角形，再把三个圆心与中间的小圆心相连，假设左右两个大圆的半径为R，下面的圆半径为r，中间的小圆半径为s，那么就可以转化成下图。
红色的边都是已知长度的，并且长度都在图中标记了出来，因为相切，所以两圆心的距离等于两圆半径之和。
那么我们可以对图中的蓝色边做文章，蓝色边的长度可以等于sqrt((R+s)^2-R^2)，也可以等于sqrt((R+r)^2-R^2)-r-s。这样我们让这两个等式相等，就可以通过R和r求出s了，不过这个方程组里有根号，不是很好解，所以我们可以用二分的方法去寻找方程的解。s求出来后我们就完成了一次操作，然后把s的值赋给r，我们就可以进行第二次操作了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
#include <functional>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF = 1e9 + 5;
const int MAXN = 100000007;
const int MOD = 1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1.0);
LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a%b); }
double R,r;
double get(double x){return sqrt(x*x + 2 * R*x) + x;}
double find(double r)//二分查找
{
int k = 200;
double l=0, rr=1e7, m;
double aim = sqrt((R + r)*(R + r) - R*R) - r;
while (k--)
{
m = (l + rr) / 2;
if (get(m) - aim > eps)
rr = m;
else
l = m;
}
return m;
}
int main()
{
int T;
int k;
scanf("%d", &T);
scanf("%lf", &R);
while (T--)
{
scanf("%d", &k);
r = R;
for (int i = 1; i <= k; i++)
r = find(r);
printf("%d %d\n", k, (int)r);
}
scanf("%d", &k);
}下一篇： 搭建ADSL自动拨号高匿代理池