ACM/ICPC 2009 宁波现场赛 Open-air Shopping Malls
这道题目是一道不错的计算几何题，题意是在一个平面上，有若干个圆（题目中称为商场）。然后需要以这些圆中的某一个圆的圆心为圆心画一个圆（题目中称为伞），使得新画的这个圆能够覆盖任何一个其它的圆的至少一半的面积。求这个圆的最小半径。
这道题的思路是，枚举每一个圆的圆心，然后以它为圆心画圆。用二分法处理半径，每枚举一个半径就尝试看能不能满足覆盖条件。然后找到最短的半径就行了。
这道题有至多 10 个 cases, 至多 20 个圆。圆心的坐标范围是 [-10000, 10000], 半径范围是 [1, 2000], 输入数据都是整数。输出要求精确到 1e-4 这样。
这题我尝试了很多次才 AC. 需要注意的问题是：
- 计算几何中如果用浮点一定要看准条件，尽量用 double. 如果数据到了 1e4 这种数量级，那么小数点要是表示到 4 位还是很有压力了。
- 这个坐标范围是 -10000 到 10000, 加上半径可以到 2000 这个条件，整个平面中可能产生的长度就可能达到 [latex]4000 + 10000 \sqrt{2}[/latex] 之多。一开始我以为令 [latex]\infty = 11111.0[/latex] 都已经便宜它了，后来 WA 才知道，唉。
- 还有那个 eps 也是要设得小一点，设置成 1e-5 都可能四舍五入错误的。其实设小一点时间完全够的。
- 我本来居然以为两圆如果是包含关系可以直接 pass, 后来 WA 了几次才发现其实如果是商场把伞给包了就跪了。
还有就是有的时候计算几何也确实容易莫名其妙地跪，比如以前似乎 POJ 如果输出 double 用 %lf 就不行（现在不知道可以了没有），用 %f 才可以。
在训练计算几何题目的时候使用数据生成器确实不错，从网上搜索标程，然后生成大量的数据，分别用标程和自己的程序来跑一跑，用专门的比较软件（比如 KDiff）比较一下，确实能够发现问题。
本题源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 | #include <cmath> #include <cstdio> #include <vector> using namespace std; const double eps = 1e-9; const double pi = acos(-1.0); const double inf = 1e18; struct point_t { double x, y; inline point_t(double a, double b) : x(a), y(b) { } inline point_t operator-(const point_t &b) const { return point_t(x - b.x, y - b.y); } inline double magsqr() const { return x * x + y * y; } inline double mag() const { return sqrt(magsqr()); } }; struct circle_t { point_t center; double radius; inline circle_t(const point_t &c, double r) : center(c), radius(r) { } }; inline int ccrel(const circle_t &a, const circle_t &b) { double d = (b.center - a.center).mag(); double p = a.radius + b.radius; double s = abs(a.radius - b.radius); if (p <= d) return -1; // Outer. if (d <= s) return 1; // Inner. return 0; // Coincide. } inline double cirarea(double radius) { return pi * radius * radius; } inline double sectarea(double radius, double theta) { return theta / (2.0 * pi) * cirarea(radius); } inline double triarea(double a, double b, double c) { double m = (a + b + c) / 2.0; return sqrt(m * (m - a) * (m - b) * (m - c)); } inline double ccarea(const circle_t &a, const circle_t &b) { //* int rel = ccrel(a, b); if (rel < 0) return 0.0f; if (rel > 0) { if (a.radius < b.radius) return cirarea(a.radius); return cirarea(b.radius); } //*/ // Otherwise, two circles must coincide. double d = (b.center - a.center).mag(); double d2 = d * d; double r2 = a.radius * a.radius; double R2 = b.radius * b.radius; double cosa = (r2 + d2 - R2) / (2.0 * a.radius * d); double cosb = (R2 + d2 - r2) / (2.0 * b.radius * d); double secta = sectarea(a.radius, 2.0 * acos(cosa)); double sectb = sectarea(b.radius, 2.0 * acos(cosb)); double quad = 2.0 * triarea(d, a.radius, b.radius); return secta + sectb - quad; } inline bool is_available( const circle_t &umbrella, const vector<circle_t> &malls) { for (int i = 0; i < malls.size(); ++i) { int rel = ccrel(umbrella, malls[i]); if (rel < 0) return false; double coincide = ccarea(umbrella, malls[i]); double halfarea = cirarea(malls[i].radius) / 2.0; if (coincide >= halfarea) continue; else return false; } return true; } int main() { // freopen("input.txt", "r", stdin); int T, n; vector<circle_t> malls; scanf("%d", &T); while (T--) { scanf("%d", &n); malls.clear(); malls.reserve(20); while (n--) { double x, y, r; scanf("%lf %lf %lf", &x, &y, &r); malls.push_back(circle_t(point_t(x, y), r)); } double result = inf; for (int i = 0; i < malls.size(); ++i) { double left = 0.0f, right = inf; circle_t umbrella(malls[i].center, inf / 2.0); while (right - left >= eps) { if (is_available(umbrella, malls)) right = umbrella.radius; else left = umbrella.radius; umbrella.radius = (right + left) / 2.0; } if (umbrella.radius < result) result = umbrella.radius; } printf("%.4lf\n", result); } return 0; } |
数据生成器源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #include <iostream> #include <cstdlib> #include <cstdio> #include <ctime> using namespace std; inline int coord() { // return rand() % 20001 - 10000; return rand() % 41 - 20; } inline int radius() { // return rand() % 2000 + 1; return rand() % 20 + 1; } int main() { freopen("input.txt", "w", stdout); srand(clock()); int t = 10000; cout << t << endl << endl; for (int i = 0; i < t; ++i) { int x = rand() % 20 + 1; cout << x << endl; for (int j = 0; j < x; ++j) cout << coord() << ' ' << coord() << ' ' << radius() << endl; cout << endl; } } |
