传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3264
题意:给你n个圆,坐标和半径,然后要在这n个圆的圆心画一个大圆,大圆与这n个圆相交的面积必须大于等于每个圆面积的一半,问你建在那个圆心半径最小,为多少。
题解:枚举这n个圆,求每个圆的最小半径,通过二分半径来求,然后取这n个的最小值即可,注意点精度就OK了。
AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;
#define si1(a) scanf("%d",&a)
#define si2(a,b) scanf("%d%d",&a,&b)
#define sd1(a) scanf("%lf",&a)
#define sd2(a,b) scanf("%lf%lf",&a,&b)
#define ss1(s) scanf("%s",s)
#define pi1(a) printf("%d\n",a)
#define pi2(a,b) printf("%d %d\n",a,b)
#define mset(a,b) memset(a,b,sizeof(a))
#define forb(i,a,b) for(int i=a;i<b;i++)
#define ford(i,a,b) for(int i=a;i<=b;i++)
typedef long long LL;
const int N=33;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-8;
int n;
struct xkn
{
double x,y,r;
double area;
}p[22],h;
double dis(xkn a,xkn b)
{
return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}
double fuck(xkn a,xkn b) //求两圆的相交面积函数。
{
double d=dis(a,b);
if(d>=a.r+b.r) return 0;
double r=(a.r>b.r?b.r:a.r);
if( d<=fabs(a.r-b.r) ) return PI*r*r;
double A1=acos( (a.r*a.r+d*d-b.r*b.r)/2/a.r/d );
double A2=acos( (b.r*b.r+d*d-a.r*a.r)/2/b.r/d );
double res=A1*a.r*a.r + A2*b.r*b.r;
res-=sin(A1)*a.r*d;
return res;
}
bool xiaohao(xkn h)
{
for(int i=0;i<n;i++)
{
double jiao=fuck(p[i],h);
if(jiao<p[i].area/2)
return false;
}
return true;
}
int main()
{
// freopen("input.txt","r",stdin);
int T;
si1(T);
while(T--)
{
si1(n);
for(int i=0;i<n;i++)
{
sd2(p[i].x,p[i].y);
sd1(p[i].r);
p[i].area=PI*p[i].r*p[i].r;
}
double Min=55555;
for(int i=0;i<n;i++)
{
double l=0,r=22222,m;
while((r-l)>eps)
{
m=(l+r)/2;
h=p[i]; h.r=m;
if(xiaohao(h))
r=m;
else
l=m;
}
if(Min>m) Min=m;
}
printf("%.4f\n",Min);
}
return 0;
}
//9253993 2013-09-30 19:54:36 Accepted 3264 0MS 320K 2260 B G++ XH_Reventon
分享到:
相关推荐
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
ACM题库,一些题目和答案,以及解题报告,传上来共享
示例 2:输入:n = 10输出:37解释:第 10 天后,总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37
杭电OnlineJudge 200-2099的解题报告
HDU 里面的2000~2099道题目的源码。谢谢支持
可拆卸核心板滤波电容电源指示灯排针复位F103--R10不焊F207--R9不焊第19引脚F103--C4焊0欧姆,C3不焊Tuesday, August 31
杭电ACM2000-2099题的解题报告
排母,核心板接口ADC 电位器扩展接口,预留模拟量Tuesday, August 31, 2021Tuesday, August 31, 2021Tuesday
求多源点到单终点的最短路(反向建图),ACM竞赛中应用的小程序。
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
杭电ACM课件2014版之 (HDUACM201403版_08)计算几何基础
2016. 增量元素之间的最大差值题目描述:给你一个下标从 0 开始的整数数组 nums ,该数组的大小为 n ,请你计算 nums[j] - nums[i]
示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入
ACM算法 计算几何基础 用于计算不规则多边形,凹多边形和凸多边形
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的 和
示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =
杭州电子科技大学ACM Steps中Chapter One-Section One的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh