HDU 3264 Open-air shopping malls ——(二分+圆交)

  纯粹是为了改进牛吃草里的两圆交模板= =。

  代码如下:

 #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 inf = ; struct circle
{
double x,y,r;
void read()
{
scanf("%lf%lf%lf",&x,&y,&r);
}
double calS()
{
return pi*r*r;
}
}c[]; double myabs(double x) {return x < ? -x : x;} double get(circle c1,circle c2)
{
double a = c1.x, b = c1.y, R = c1.r;
double x = c2.x, y = c2.y, r = c2.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 n;
bool solve(circle now)
{
for(int i=;i<=n;i++)
{
if(get(now,c[i]) >= 0.5*c[i].calS()) ;
else return ;
}
return ;
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=;i<=n;i++) c[i].read();
double ans = inf;
for(int i=;i<=n;i++)
{
circle now = c[i];
double L = , R = inf;
int CNT = ;
while(CNT--)
{
double mid = (L + R) / ;
now.r = mid;
if(solve(now)) R = mid;
else L = mid;
}
ans = min(ans, R);
}
printf("%.4f\n",ans);
}
return ;
}
上一篇:NET SignalR 与 LayIM2.0


下一篇:day-06数据类型与深浅拷贝