SRM 249 DIV1 Hard CultureGrowth

問題 Editorial

問題

初期状態として、整数座標上の点がいくつか与えられる(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.;
	}
};