zstuoj 4243 牛吃草 ——(二分+两圆交)

时间:2023-02-01 16:37:51

  这题上次补了以后忘记写博客了,现在补一下。

  有两个注意点,第一是两圆相交的模板。可以通过任意一种情况手推出来。

  第二是,实数二分要注意不用ans记录为妙,因为可能因为eps过小,导致ans无法进入记录答案的语句中(ans过大可能又会有误差),直接用一个l或者r记录一下即可。

  代码如下:

 #include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <math.h>
using namespace std;
const int N = + ;
typedef long long ll;
const double eps = 1e-;
const double pi = acos(-1.0); double myabs(double x) {return x < ? -x : x;} double get(double a,double b,double x,double y,double R,double r)
{
double dx = myabs(a-x), dy = myabs(b-y);
double d = sqrt(dx*dx+dy*dy);
if(d > R + r) return 0.0;
if(R < r) swap(R,r);
if(d < R-r) return pi*r*r;
double A = 2.0*acos((R*R+d*d-r*r)/(2.0*R*d));
double B = 2.0*acos((r*r+d*d-R*R)/(2.0*r*d));
double s1 = 0.5*A*R*R + 0.5*B*r*r;
double s2 = 0.5*R*R*sin(A) + 0.5*r*r*sin(B);
return s1 - s2;
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
double a,b,x,y,R;
scanf("%lf%lf%lf%lf%lf",&a,&b,&x,&y,&R);
double dx = myabs(a-x), dy = myabs(b-y);
double d = sqrt(dx*dx+dy*dy);
double Area = pi * R * R;
//double ans;
double l = 0.0, r = 100000000.0;
int T = ;
while(T--)
{
double mid = (l+r) / 2.0;
double area = get(a,b,x,y,R,mid);
if(area*2.0 > Area) r = mid; //{ans = mid; r = mid;}
else l = mid;
}
printf("%.4f\n",r);
//printf("%.4f\n",ans);
}
return ;
}