HDOJ 3264 Open-air shopping malls

计算几何的圆的模板题+二分判断

题目中给了n个圆，要求：在这n个圆中取某个圆的圆心，然后找到最小的半径，使得这个新的圆与这n个圆的相交面积，会不小于这n个圆的面积的一半

说起来，很绕口，但是因为n不大，是可以枚举的！

对于每个圆心，我们都求一个最小的半径，然后n个值中间取最小的就是答案

那么，如何求得这个最小呢？很简单，化计算性问题为判定性问题

我们二分半径，然后验证这个半径会不会满足题中面积的条件

剩下的：就是靠kuangbin模板啊：就是如何已经两个圆的圆心和半径，然后求相交的面积

代码如下：

#include<bits/stdc++.h>
using namespace std;

int t,n;
double ans;

const int maxn=30;
const double eps=1e-6;
const double pi=acos(-1.0);
int sgn(double x){
	if (fabs(x)<eps) return 0;
	if (x<0) return -1;
	return 1;
}

struct Point{
	double x,y;
	Point(){}
	Point(double _x,double _y){
		x=_x;
		y=_y;
	}
	double distance(Point p){
		return hypot(x-p.x,y-p.y);
	}
};

struct circle{
	Point p;
	double r;
	circle(){}
	circle(Point _p,double _r){
		p=_p;
		r=_r;
	}
	circle(double x,double y,double _r){
		p=Point(x,y);
		r=_r;
	}
	double area(){
		return pi*r*r;
	}
	int relationcircle(circle v){
		double d=p.distance(v.p);
		if (sgn(d-r-v.r)>0) return 5;
		if (sgn(d-r-v.r)==0) return 4;
		double l=fabs(r-v.r);
		if (sgn(d-r-v.r)<0&&sgn(d-l)>0) return 3;
		if (sgn(d-l)==0) return 2;
		if (sgn(d-l)<0) return 1;
	}
	double areacircle(circle v){
		int rel=relationcircle(v);
		if (rel>=4) return 0.0;
		if (rel<=2) return min(area(),v.area());
		double d=p.distance(v.p);
		double hf=(r+v.r+d)/2.0;
		double ss=2*sqrt(hf*(hf-r)*(hf-v.r)*(hf-d));
		double a1=acos((r*r+d*d-v.r*v.r)/(2.0*r*d));
		a1=a1*r*r;
		double a2=acos((v.r*v.r+d*d-r*r)/(2.0*v.r*d));
		a2=a2*v.r*v.r;
		return a1+a2-ss;
	}
}c[maxn];

bool ok(){
	for(int i=1;i<=n;i++){
		double a1=c[n+1].areacircle(c[i]);
		double a2=c[i].area();
		if (a2-2*a1>eps) return false;
	}
	return true;
}

int main(){
	//freopen("input.txt","r",stdin);
	double x,y,r;
	scanf("%d",&t);
	while(t--){
		ans=100000.0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%lf%lf%lf",&x,&y,&r);
			c[i]=circle(x,y,r);
		}
		for(int i=1;i<=n;i++){
			double L=0,R=10000,mid;
			while(L+eps<=R){
				mid=(L+R)/2.0;
				c[n+1]=circle(c[i].p,mid);
				if (ok()) R=mid;
				else L=mid;
			}
			ans=min(ans,mid);
		}
		printf("%.4lf\n",ans);
	}
	return 0;
}