題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3264

題目大意：給出平面上n個圓的圓心和半徑，求一個大圓，它的圓心與某個給定圓的圓心重合，且對于每一個給定的圓，大圓至少覆蓋面積的一半，求出滿足要求的大圓的最小半徑。

分析：由于所求的大圓圓心只有n種選擇，我們可以枚舉大圓的圓心，然后求能夠滿足要求的最小半徑，取半徑最小的方案即可。

　　直接求滿足要求的最小半徑比較困難，但若我們已經知道一個半徑，判斷它時候覆蓋了每一個圓至少一半的面積，問題就簡單那多了。如果不會求圓的重合面積的話請移步??????????????????????? http://www.cnblogs.com/evan-oi/archive/2012/03/14/2395989.html

所以枚舉圓心之后，二分查找圓的最小半徑就可以了。總時間復雜度為O(n^2logL),L為查找的區間長度(對于這種n奇小的題目來說復雜度基本上無視，只要不是指數級就應該都能過)

?

附代碼：

View Code #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
#define MaxN 25
#define INF 20000000
#define pi 3.141592653
#define zero 1e-8
struct atp
{
double x,y,r;
}p[MaxN];
int n;
double ans;
void init()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].r);
}

inline double dis(atp a,atp b)
{
return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double calc(atp a,double ra,atp b)
{
double t=0,d,rb=b.r;
d=dis(a,b);
if (ra<rb) swap(ra,rb);
if (d>=ra+rb) return 0;
if (d<=ra-rb) return pi*rb*rb;

double t1=acos((ra*ra+d*d-rb*rb)/(2*ra*d));
double t2=acos((rb*rb+d*d-ra*ra)/(2*rb*d));
t=t1*ra*ra+t2*rb*rb-d*ra*sin(t1);
return t;
}

bool check(int x,double r)
{
for (int i=1;i<=n;i++)
if (2*calc(p[x],r,p[i]) <pi*p[i].r*p[i].r) return false;
return true;
}

double get(int i)
{
double l,r,mid;
l=0;r=30000;
while (l+zero<=r)
{
mid=(l+r)/2;
if (check(i,mid)) r=mid-zero; else l=mid+zero;
}
return mid;
}

void work()
{
double tans;ans=INF;
for (int i=1;i<=n;i++)
{tans=get(i);if (ans>tans) ans=tans;}
printf("%.4lf\n",ans);
}
int main()
{
freopen("in","r",stdin);
freopen("out","w",stdout);
int Case;
scanf("%d",&Case);
while (Case--)
init(),work();
return 0;
}

轉載于:https://www.cnblogs.com/evan-oi/archive/2012/03/14/2396027.html

總結

以上是生活随笔為你收集整理的HDU 3264 Open-air shopping malls的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。