SRM 249 DIV1 Hard CultureGrowth
問題
初期状態として、整数座標上の点がいくつか与えられる(xs, ys)。
いつでも、任意の点2つ(p, q)に対して((p.x + q.x) / 2.0, (q.x + q.y) / 2.0)の点を作ることができる。
この操作を無限にどんなふうにでも繰り返せるとき、全ての点を被覆する多角形の面積を求めよ
解答
凸包の面積を計算するだけ
コード
#include <vector> #include <algorithm> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define pb(x) push_back(x) using namespace std; typedef long long ll; struct P { typedef int T; typedef ll T2; //T2は{a*b | a:T, b:T}を含むタイプ T x, y; P(T x_, T y_): x(x_), y(y_) {} P(): x(0), y(0) {} }; inline bool operator<(const P& a, const P& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); } inline P::T2 cross(const P& a, const P& b) { return (P::T2)a.x*b.y - (P::T2)a.y*b.x; } inline int ccw(const P& a, const P& b, const P& c) { int ax = b.x - a.x, ay = b.y - a.y, bx = c.x - a.x, by = c.y - a.y; P::T2 t = (P::T2)ax*by - (P::T2)ay*bx; if (t > 0) return 1; if (t < 0) return -1; if((P::T2)ax*bx + (P::T2)ay*by < 0) return +2; if((P::T2)ax*ax + (P::T2)ay*ay < (P::T2)bx*bx + (P::T2)by*by) return -2; return 0; } vector<P> convex_hull(vector<P> ps) { int n = ps.size(), k = 0; sort(ps.begin(), ps.end()); vector<P> ch(2*n); for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull while (k >= 2 && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k; for (int i = n-2, t = k+1; i >= 0; ch[k++] = ps[i--]) // upper-hull while (k >= t && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k; ch.resize(k-1); return ch; } P::T2 area(const vector<P>& o) { P::T2 A = 0; for (int i = 0; i < o.size(); ++i) A += cross(o[i], o[(i+1)%o.size()]); return A; } struct CultureGrowth { double finalTray(vector <int> xs, vector <int> ys) { vector<P> ps; rep(i, xs.size()) ps.pb(P(xs[i], ys[i])); return area(convex_hull(ps)) / 2.; } };