ACM/ICPC 2010 杭州现场赛 Rotational Painting 题解
不错的计算几何题。题目输入若干个简单多边形（允许存在凹多边形，但是多边形的边不会交叉），它们的质量是均匀的。要求计算每个多边形在水平线上有多少种稳定的摆放方式。其中一个比较特别的地方就是，如果重心和支撑线段所作的垂心与支撑线段的端点重合，视为不稳定的状态。具体原题的配图中说得很清楚，就不多说了。多边形的边数可能达到 50000 条。
思路应该是比较清晰的：首先求多边形的凸包，然后求多边形的重心；再枚举凸包上的每一条边，从重心向枚举的边作垂线；如果所作的垂线能够与边规范相交，那么这种情况是一种稳定情况。
思路确实很简单，但是写起来就有很多东西要写。比如凸包就是一个比较长的东西了，然后求重心又涉及到多边形的三角形分割啥的，还有垂线与边相交的判定也是有点麻烦的。
这道题我 WA 了一次，是因为我计算重心的时候，用的是凸包而不是原多边形。
本题源代码
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 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 | #include <cmath> #include <vector> #include <cstdio> #include <algorithm> using namespace std; ///////////// // Numbers // ///////////// const double eps = 1e-6; inline int sgn(double a) { return a > eps ? 1 : a < -eps ? -1 : 0; } inline bool eq(double a, double b) { return !sgn(a - b); } inline bool lt(double a, double b) { return sgn(a - b) < 0; } inline bool gt(double a, double b) { return sgn(a - b) > 0; } //////////// // Points // //////////// struct point { double x, y; inline point() : x(0.0), y(0.0) { } inline point(double x, double y) : x(x), y(y) { } inline point operator+(const point &b) const { return point(x + b.x, y + b.y); } inline point operator-(const point &b) const { return point(x - b.x, y - b.y); } inline point operator*(double k) const { return point(x * k, y * k); } inline point operator/(double k) const { return point(x / k, y / k); } inline point &operator+=(const point &b) { x += b.x; y += b.y; return *this; } inline point &operator-=(const point &b) { x -= b.x; y -= b.y; return *this; } inline point &operator*=(double k) { x *= k; y *= k; return *this; } inline point &operator/=(double k) { x /= k; y /= k; return *this; } inline bool operator==(const point &b) const { return eq(x, b.x) && eq(y, b.y); } inline double magsqr() const { return x * x + y * y; } }; inline double cross(const point &a, const point &b) { return a.x * b.y - a.y * b.x; } inline double dot(const point &a, const point &b) { return a.x * b.x + a.y * b.y; } inline double ccw(const point &p, const point &a, const point &b) { return cross(a - p, b - p); } /////////// // Lines // /////////// struct line { point a, b; inline line(const point &a, const point &b) : a(a), b(b) { } inline point vec() const { return b - a; } }; inline point inpll(const line &la, const line &lb) { double u = cross(la.vec(), point(lb.b - la.b)); double v = cross(la.vec(), point(lb.a - la.b)); return (lb.b * v - lb.a * u) / (v - u); } inline int relpl(const point &p, const line &l) { return sgn(cross(p - l.a, l.vec())); // 0: on; -1: .|; 1: |.. } inline int relps(const point &p, const line &s) { int rp = relpl(p, s); if (rp) return rp * 3; // -3: .|; 3: |.. point psa = s.a - p, psb = s.b - p; int r = sgn(dot(psa, psb)); if (r < 0) return 0; // The point is on the segment between end-points. if (r == 0) return 1; // The point is at either end-point. return 2; // The point is on the line s. } inline point plupl(const point &p, const line &l) { point u = l.vec(), v = p - l.a; return l.a + u * dot(u, v) / u.magsqr(); } ////////////// // Polygons // ////////////// typedef vector<point> polygon; inline point tricore(const point &a, const point &b, const point &c) { return point((a.x + b.x + c.x) / 3.0, (a.y + b.y + c.y) / 3.0); } inline point polycore(const polygon &poly) { point core(0.0, 0.0); double mass = 0.0; for (int i = 2; i < poly.size(); ++i) { point c = tricore(poly[0], poly[i - 1], poly[i]); double m = ccw(poly[0], poly[i - 1], poly[i]); core += (c *= m); mass += m; } return core /= mass; } struct graham_scan { vector<bool> instack; vector<int> indices; inline static bool lessthan(const point &a, const point &b) { if (eq(a.y, b.y)) return lt(a.x, b.x); return lt(a.y, b.y); } inline void scan(const polygon &po, int begin, int end, int delta) { for (int i = begin; i != end; i += delta) { if (instack[i]) continue; while (indices.size() >= 2) { const point &a = po[indices.back()]; const point &p = po[indices[indices.size() - 2]]; if (sgn(ccw(p, a, po[i])) <= 0) { instack[indices.back()] = false; indices.pop_back(); } else break; } instack[i] = true; indices.push_back(i); } } inline void solve_indices(polygon &poly) // Incoming poly will be changed. { instack.clear(); instack.resize(poly.size(), false); indices.clear(); indices.reserve(poly.size() + 1); sort(poly.begin(), poly.end(), lessthan); poly.resize(unique(poly.begin(), poly.end()) - poly.begin()); indices.push_back(0); scan(poly, 1, poly.size(), 1); scan(poly, poly.size() - 1, -1, -1); indices.pop_back(); } inline polygon polygon_from_indices(const polygon &original) { polygon result; result.reserve(indices.size()); for (int i = 0; i < indices.size(); ++i) result.push_back(original[indices[i]]); return result; } }; graham_scan graham; inline int stable_side_count(const polygon &original) { polygon sorted = original; graham.solve_indices(sorted); polygon convex = graham.polygon_from_indices(sorted); int result = 0; point core = polycore(original); for (int i = 0; i < convex.size(); ++i) { int j = (i + 1) % convex.size(); line edge(convex[i], convex[j]); point plumb = plupl(core, edge); if (relps(plumb, edge) == 0) ++result; } return result; } int main() { // freopen("input.txt", "r", stdin); int T, n; scanf("%d", &T); while (T--) { polygon poly; scanf("%d", &n); poly.reserve(n); while (n--) { double x, y; scanf("%lf %lf", &x, &y); poly.push_back(point(x, y)); } printf("%d\n", stable_side_count(poly)); } 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 | #include <iostream> #include <cstdlib> #include <cstdio> #include <ctime> using namespace std; int main() { freopen("input.txt", "w", stdout); srand(clock()); int t = 1000; cout << t << endl << endl; while (t--) { int n = rand() % 10 + 3; cout << n << endl << endl; while (n--) cout << rand() % 100 << ' ' << rand() % 100 << endl; cout << endl << endl; } return 0; } |
