题目描述老麦克唐纳有一个农场农场里有一头牛和一个半径为100100100码的圆形围栏。他计划将牛拴在围栏边界上的一根柱子上。他希望牛能够吃到围栏内三分之一面积的草。绳子应该有多长你需要解决这个问题的推广形式。输入格式输入第一行是一个正整数表示测试用例的数量。每个测试用例包含两个数字RRR半径1≤R≤10001 \leq R \leq 10001≤R≤1000的整数和PPP比例0.0≤P≤0.50.0 \leq P \leq 0.50.0≤P≤0.5的实数。两个测试用例之间有一个空行。输出格式对于每个测试用例按样例格式输出一行。PPP和答案四舍五入到两位小数。每个测试用例的输出后跟一个空行。样例输入1 100 0.33样例输出R 100, P 0.33, Rope 13.24题目分析问题的本质这是一个几何求解问题。给定一个半径为RRR的圆在圆周上取一点作为拴牛点用长度为LLL的绳子将牛拴在该点。牛可以吃到绳子覆盖范围内的草即半径为LLL的圆与半径为RRR的圆的交集区域。需要求绳子长度LLL使得牛能吃到的草的面积等于给定比例PPP乘以大圆面积。几何关系设大圆牧场半径RRR圆心OOO拴牛点P0P_0P0​在大圆圆周上绳子长度LLL牛的活动区域是以P0P_0P0​为圆心、LLL为半径的圆牛能吃到的草是大圆与小圆的交集区域由于对称性拴牛点位于圆周上时交集的形状由两个圆的相交部分决定。数学推导设两个圆的圆心距离为dRd RdR拴牛点在大圆上半径分别为RRR和LLL。两圆相交部分的面积公式为SR2cos⁡−1(d2R2−L22dR)L2cos⁡−1(d2L2−R22dL)−12(−dRL)(dR−L)(d−RL)(dRL) S R^2 \cos^{-1}\left(\frac{d^2 R^2 - L^2}{2dR}\right) L^2 \cos^{-1}\left(\frac{d^2 L^2 - R^2}{2dL}\right) - \frac{1}{2} \sqrt{(-dRL)(dR-L)(d-RL)(dRL)}SR2cos−1(2dRd2R2−L2​)L2cos−1(2dLd2L2−R2​)−21​(−dRL)(dR−L)(d−RL)(dRL)​由于dRd RdR公式可简化。设αarccos⁡(2R2−L22R2)\alpha \arccos\left(\frac{2R^2 - L^2}{2R^2}\right)αarccos(2R22R2−L2​)βarccos⁡(L2R)\beta \arccos\left(\frac{L}{2R}\right)βarccos(2RL​)则相交部分面积SR2αL2β−12RLsin⁡(2β) S R^2 \alpha L^2 \beta - \frac{1}{2} R L \sin(2\beta)SR2αL2β−21​RLsin(2β)或者等价形式SR2αL2β−R2sin⁡α S R^2 \alpha L^2 \beta - R^2 \sin \alphaSR2αL2β−R2sinα注意这里需要验证等式的正确性。实际上从几何关系可得SR2cos⁡−1(1−L22R2)L2cos⁡−1(L2R)−L24R2−L2 S R^2 \cos^{-1}\left(1 - \frac{L^2}{2R^2}\right) L^2 \cos^{-1}\left(\frac{L}{2R}\right) - \frac{L}{2} \sqrt{4R^2 - L^2}SR2cos−1(1−2R2L2​)L2cos−1(2RL​)−2L​4R2−L2​其中4R2−L22Rsin⁡(α/2)\sqrt{4R^2 - L^2} 2R \sin(\alpha/2)4R2−L2​2Rsin(α/2)。面积比例PPP是牛能吃到的草占整个牧场的比例PSπR2 P \frac{S}{\pi R^2}PπR2S​即P1π[cos⁡−1(1−L22R2)L2R2cos⁡−1(L2R)−L2R4−L2R2] P \frac{1}{\pi} \left[ \cos^{-1}\left(1 - \frac{L^2}{2R^2}\right) \frac{L^2}{R^2} \cos^{-1}\left(\frac{L}{2R}\right) - \frac{L}{2R} \sqrt{4 - \frac{L^2}{R^2}} \right]Pπ1​[cos−1(1−2R2L2​)R2L2​cos−1(2RL​)−2RL​4−R2L2​​]令xL/Rx L / RxL/R则方程简化为P1π[cos⁡−1(1−x22)x2cos⁡−1(x2)−x24−x2] P \frac{1}{\pi} \left[ \cos^{-1}\left(1 - \frac{x^2}{2}\right) x^2 \cos^{-1}\left(\frac{x}{2}\right) - \frac{x}{2} \sqrt{4 - x^2} \right]Pπ1​[cos−1(1−2x2​)x2cos−1(2x​)−2x​4−x2​]求解方法由于方程无法解析求解需要使用数值方法如二分法求xxx然后得到LxRL xRLxR。参考代码// Dont Have A Cow, Dude// UVa ID: 358// Verdict: Accepted// Submission Date: 2016-07-06// UVa Run Time: 0.040s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constdoublePI2.0*acos(0.0);intmain(){ios::sync_with_stdio(false);intcases;string R,P;cincases;for(inti1;icases;i){// 测试用例间输出空行if(i1)coutendl;cinRP;doublerstod(R),pstod(P);doublelow0.0,up2.0*r;// 绳子长度范围0 到直径intiterations0;// 二分查找while(fabs(low-up)1e-7iterations40){doublemiddle(lowup)/2.0;// 计算当前绳子长度下的面积比例doublea1acos((2.0*r*r-middle*middle)/(2.0*r*r));doublea2acos(middle/(2.0*r));doublenext_p(r*r*a1middle*middle*a2-r*r*sin(a1))/(PI*r*r);if(next_pp)lowmiddle;elseupmiddle;}coutR R;cout, P fixedsetprecision(2)p;cout, Rope fixedsetprecision(2)lowendl;}return0;}