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; }