1 2 0 0 1 2 0 1
2.0822
求一个最小半径使得圆心位于 某一个圆的圆心时，可以覆盖n个圆中每一个圆的至少一半面积。
二分半径，然后枚举圆心，判断可行性。
代码：
/* ***********************************************
Author :rabbit
Created Time :2014/4/20 9:39:31
File Name :8.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-10
#define pi acos(-1.0)
typedef long long ll;
int dcmp(double x){
if(fabs(x)<eps)return 0;
return x>0?1:-1;
}
struct Point{
double x,y;
Point(double _x=0,double _y=0){
x=_x;y=_y;
}
};
Point operator + (Point a,Point b){
return Point(a.x+b.x,a.y+b.y);
}
Point operator - (Point a,Point b){
return Point(a.x-b.x,a.y-b.y);
}
Point operator * (Point a,double p){
return Point(a.x*p,a.y*p);
}
Point operator / (Point a,double p){
return Point(a.x/p,a.y/p);
}
bool operator < (const Point &a,const Point &b){
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
bool operator == (const Point &a,const Point &b){
return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double Dot(Point a,Point b){
return a.x*b.x+a.y*b.y;
}
double Length(Point a){
return sqrt(Dot(a,a));
}
double Angle(Point a,Point b){
return acos(Dot(a,b)/Length(a)/Length(b));
}
double angle(Point a){
return atan2(a.y,a.x);
}
double Cross(Point a,Point b){
return a.x*b.y-a.y*b.x;
}
Point vecunit(Point x){
return x/Length(x);
}
Point Normal(Point x){
return Point(-x.y,x.x);
}
Point Rotate(Point a,double rad){
return Point(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}
struct Line{
Point p,v;
double ang;
Line(){}
Line(Point P,Point v):p(P),v(v){
ang=atan2(v.y,v.x);
}
bool operator < (const Line &L) const {
return ang<L.ang;
}
Point point(double a){
return p+(v*a);
}
};
bool SegmentIntersection(Point a1,Point a2,Point b1,Point b2){
double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1),
c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
struct Circle{
Point c;
double r;
Circle(){}
Circle(Point c,double r):c(c),r(r){}
Point point(double a){
return Point(c.x+cos(a)*r,c.y+sin(a)*r);
}
};
double area_cir_cir(Circle a,Circle b){
double d=Length(a.c-b.c),r1=a.r,r2=b.r,r;
if(r1+r2<=d)return 0;
else if(fabs(r1-r2)>=d){
r=min(r1,r2);
return pi*r*r;
}
else{
double a1=(r1*r1+d*d-r2*r2)/(2*r1*d);
double a2=(r2*r2+d*d-r1*r1)/(2*r2*d);
a1=2*acos(a1);
a2=2*acos(a2);
return (r1*r1*(a1-sin(a1))+r2*r2*(a2-sin(a2)))/2;
}
}
Circle s[100];
int main()
{
int T,n;
cin>>T;
while(T--){
cin>>n;
for(int i=0;i<n;i++)cin>>s[i].c.x>>s[i].c.y>>s[i].r;
double left=0,right=100000;
while(left+eps<right){
double mid=(left+right)/2;
int flag=0;
for(int i=0;i<n;i++){
int flag1=1;
Circle p;p.c=s[i].c;p.r=mid;
for(int j=0;j<n;j++){
double s1=area_cir_cir(p,s[j]);
if(s1<pi*s[j].r*s[j].r/2){
flag1=0;break;
}
}
if(flag1){
flag=1;break;
}
}
// cout<<"han "<<left<<" "<<right<<" "<<mid<<endl;
if(!flag)left=mid;
else right=mid;
}
printf("%.4lf\n",left);
}
}
HDU 3264 两圆相交，枚举+二分,布布扣,bubuko.com
原文：http://blog.csdn.net/xianxingwuguan1/article/details/24304175