欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2017 ACM-ICPC 亚洲区(南宁赛区)网络赛 G. Finding the Radius for an Inserted Circle(计算几何,二分)

程序员文章站 2022-06-02 20:08:12
...

Finding the Radius for an Inserted Circle

Three circles C_{a}CaC_{b}Cb, and C_{c}Cc, all with radius RR and tangent to each other, are located in two-dimensional space as shown in Figure 11. A smaller circle C_{1}C1 with radius R_{1}R1 (R_{1}<RR1<R) is then inserted into the blank area bounded by C_{a}CaC_{b}Cb, and C_{c}Cc so that C_{1}C1 is tangent to the three outer circles, C_{a}CaC_{b}Cb, and C_{c}Cc. Now, we keep inserting a number of smaller and smaller circles C_{k}\ (2 \leq k \leq N)Ck (2kN) with the corresponding radius R_{k}Rk into the blank area bounded by C_{a}CaC_{c}Cc and C_{k-1}Ck1 (2 \leq k \leq N)(2kN), so that every time when the insertion occurs, the inserted circle C_{k}Ck is always tangent to the three outer circles C_{a}CaC_{c}Cc and C_{k-1}Ck1, as shown in Figure 11

2017 ACM-ICPC 亚洲区(南宁赛区)网络赛 G. Finding the Radius for an Inserted Circle(计算几何,二分)

Figure 1.

(Left) Inserting a smaller circle C_{1}C1 into a blank area bounded by the circle C_{a}CaC_{b}Cb and C_{c}Cc.

(Right) An enlarged view of inserting a smaller and smaller circle C_{k}Ck into a blank area bounded by C_{a}CaC_{c}Cc and C_{k-1}Ck1 (2 \leq k \leq N2kN), so that the inserted circle C_{k}Ck is always tangent to the three outer circles, C_{a}CaC_{c}Cc, and C_{k-1}Ck1.

Now, given the parameters RR and kk, please write a program to calculate the value of R_{k}Rk, i.e., the radius of the k-thkth inserted circle. Please note that since the value of R_kRk may not be an integer, you only need to report theinteger part of R_{k}Rk. For example, if you find that R_{k}Rk = 1259.89981259.8998 for some kk, then the answer you should report is 12591259.

Another example, if R_{k}Rk = 39.102939.1029 for some kk, then the answer you should report is 3939.

Assume that the total number of the inserted circles is no more than 1010, i.e., N \leq 10N10. Furthermore, you may assume \pi = 3.14159π=3.14159. The range of each parameter is as below:

1 \leq k \leq N1kN, and 10^{4} \leq R \leq 10^{7}104R107.

Input Format

Contains l + 3l+3 lines.

Line 11ll ----------------- the number of test cases, ll is an integer.

Line 22RR ---------------- RR is a an integer followed by a decimal point,then followed by a digit.

Line 33kk ---------------- test case #11kk is an integer.

\ldots

Line i+2i+2kk ----------------- test case # ii.

\ldots

Line l +2l+2kk ------------ test case #ll.

Line l + 3l+3-11 ---------- a constant -11 representing the end of the input file.

Output Format

Contains ll lines.

Line 11kk R_{k}Rk ----------------output for the value of kk and R_{k}Rk at the test case #11, each of which should be separated by a blank.

\ldots

Line iikk R_{k}Rk ----------------output for kk and the value of R_{k}Rk at the test case # ii, each of which should be separated by a blank.

Line llkk R_{k}Rk ----------------output for kk and the value ofR_{k}Rk at the test case # ll, each of which should be separated by a blank.

样例输入

1
152973.6
1
-1

样例输出

1 23665
题意:这道题就是给你三个一模一样的圆,左边一个右边一个下面一个,三个圆两两相切,然后在这三个圆中间的地方找一个小圆,要求这个小圆与这三个大圆相切,这被称为一次操作,然后第二次操作的时候,就把下面的大圆替换成那个小圆,然后从这两个大圆和一个小圆中间再找一个更小的圆也与它们相切,最后问你经过k次操作后那个小圆的半径是多少。


思路:我们可以把三个圆的圆心两两相连,连成一个三角形,再把三个圆心与中间的小圆心相连,假设左右两个大圆的半径为R,下面的圆半径为r,中间的小圆半径为s,那么就可以转化成下图。

2017 ACM-ICPC 亚洲区(南宁赛区)网络赛 G. Finding the Radius for an Inserted Circle(计算几何,二分)

红色的边都是已知长度的,并且长度都在图中标记了出来,因为相切,所以两圆心的距离等于两圆半径之和。

那么我们可以对图中的蓝色边做文章,蓝色边的长度可以等于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);
}