本文主要是介绍HDU 3264 Open-air shopping malls（二分+圆交），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
HDU 3264 Open-air shopping malls
题目链接
题意：给定一些圆，求以一个圆的圆心为圆心，自己定一个半径，使得和其他所有圆交面积都大于该圆的一半，求这个半径的最小值
思路：很显然的二分半径，判断方法就枚举一个圆心，然后和每个圆求圆交面积即可
代码：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;const int N = 25;
const double pi = acos(-1.0);
const double eps = 1e-8;
int t, n;
struct Circle {double x, y, r;void read() {scanf("%lf%lf%lf", &x, &y, &r);}
} c[N], o;double dis(double x1, double y1, double x2, double y2) {double dx = x1 - x2;double dy = y1 - y2;return sqrt(dx * dx + dy * dy);
}double area(Circle c) {return c.r * c.r * pi;
}double dcmp(double x) {if (fabs(x) < eps) return 0.0;return x;
}double cal(Circle c1, Circle c2) {double a = dis(c1.x, c1.y, c2.x, c2.y), b = c1.r, c = c2.r;double r1 = c1.r, r2 = c2.r;if (dcmp(a - b - c) >= 0) return 0.0;double minr = min(b, c);if (dcmp(a - fabs(b - c)) <= 0) return minr * minr * pi;double cta1 = acos((a * a + b * b - c * c) / 2 / (a * b));double cta2 = acos((a * a + c * c - b * b) / 2 / (a * c));double s1 = r1 * r1 * cta1 - r1 * r1 * sin(cta1) * (a * a + b * b - c * c) / 2 / (a * b);double s2 = r2 * r2 * cta2 - r2 * r2 * sin(cta2) * (a * a + c * c - b * b) / 2 / (a * c);return s1 + s2;
}bool check() {for (int i = 0; i < n; i++)if (cal(o, c[i]) < area(c[i]) / 2) return false;return true;
}bool judge(double r) {for (int i = 0; i < n; i++) {o.x = c[i].x; o.y = c[i].y; o.r = r;if (check()) return true;}return false;
}int main() {scanf("%d", &t);while (t--) {scanf("%d", &n);for (int i = 0; i < n; i++)c[i].read();double l = 0, r = 1e5;for (int i = 0; i < 100; i++) {double mid = (l + r) / 2;if (judge(mid)) r = mid;else l = mid;}printf("%.4lf\n", l);}return 0;
}这篇关于HDU 3264 Open-air shopping malls（二分+圆交）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
