首页 > 代码库 > [hdu 3264] Open-air shopping malls(二分+两圆相交面积)
[hdu 3264] Open-air shopping malls(二分+两圆相交面积)
题目大意是:先给你一些圆,你可以任选这些圆中的一个圆点作圆,这个圆的要求是:你画完以后。这个圆要可以覆盖之前给出的每一个圆一半以上的面积,即覆盖1/2以上每一个圆的面积。
比如例子数据,选左边还是选右边没差别,红色的圆为答案(选了左边的圆点),它覆盖了左边圆的1/2以上,也覆盖了右边圆的1/2以上。
知道了怎样求两圆面积交。那么这道题就简单了。仅仅要二分答案,然后枚举每个圆点,假设全都覆盖了1/2以上就继续二分,最后答案就得出来了。
#include<iostream> #include<cmath> using namespace std; #define pi acos(-1.0) #define eps 1e-7 typedef struct node { int x; int y; double r; }Circle; int n; Circle cc[22]; double AREA(Circle a, Circle b) { double d = sqrt((a.x-b.x)*(a.x-b.x)*1.0 + (a.y-b.y)*(a.y-b.y)); double r1 = a.r, r2 = b.r; if (d >= r1+r2) return 0; if (r1>r2) { double tmp = r1; r1 = r2; r2 = tmp; } if(r2 - r1 >= d) return pi*r1*r1; double ang1=acos((r1*r1+d*d-r2*r2)/(2*r1*d)); double ang2=acos((r2*r2+d*d-r1*r1)/(2*r2*d)); return ang1*r1*r1 + ang2*r2*r2 - r1*d*sin(ang1); } bool judge(double r) { int i, j; for(i = 0; i < n; i++) { Circle t = cc[i]; t.r = r; for(j = 0; j < n; j++) { if(AREA(cc[j], t) < pi*cc[j].r*cc[j].r/2) break; } if(j == n) return true; } return false; } int main() { int tot; scanf("%d", &tot); while(tot--) { scanf("%d\n", &n); for(int i = 0; i < n; i++) scanf("%d%d%lf", &cc[i].x, &cc[i].y, &cc[i].r); double l = 0, r = 1<<16; while(l + eps < r) { double mid = (l + r) / 2; if(judge(mid)) r = mid; else l = mid; } printf("%.4lf\n", r); } return 0; }
[hdu 3264] Open-air shopping malls(二分+两圆相交面积)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。