用整形实现的。封装好了。就是不知道为什么有点慢。
code(373ms):
#include <iostream> #include <set> using namespace std; #define DEBUG 0 typedef long long LL; typedef LL LT; template <typename T> T sq(T x) { return x * x; } int sgn(LT x) { return x < 0 ? -1 : (x > 0 ? 1 : 0); } struct VEC { LT x, y; VEC operator + (const VEC& b) const { return VEC{x + b.x, y + b.y}; } bool operator == (const VEC& b) const { return x == b.x && y == b.y; } bool operator < (const VEC& b) const { return y != b.y ? y < b.y : x < b.x; } VEC operator - (const VEC& b) const { return VEC{x - b.x, y - b.y}; } LT len2() const { return sq(x) + sq(y); } LT dist2(const VEC& b) const { return (*this - b).len2(); } //Might overflow LT operator * (const VEC& b) const { return x * b.x + y * b.y; } LT operator ^ (const VEC& b) const { return x * b.y - y * b.x; } bool ToLeftTest(const VEC& b) const { return (*this ^ b) > 0; } bool ToRightTest(const VEC& b) const { return (*this ^ b) < 0; } LT cross(const VEC& p1, const VEC& p2) const { return (p1 - *this) ^ (p2 - *this); } void input() { cin >> x >> y; } }; struct down_sgn { int operator () (LT x) const { return sgn(x); } }; struct up_sgn { int operator () (LT x) const { return -sgn(x); } }; template <class XSGN> struct HalfConvexHull { #define xsgn XSGN() struct CMPX { bool operator () (const VEC& a, const VEC& b) { return xsgn(a.x - b.x) < 0; } }; typedef set<VEC, CMPX> SE; SE s; typedef typename SE::iterator IT; LT area2; //to (0, 0) IT it; HalfConvexHull() : area2(0) {} //The convex mustn't be degenerate //0: out //1: on //2: in int relation(const VEC& p) { it = s.lower_bound(p); if (it == s.end()) return 0; if (it == s.begin()) { if (xsgn(p.x - it->x) < 0) return 0; else return xsgn(p.y - it->y) + 1; } auto bef = it; --bef; return sgn((*it - *bef) ^ (p - *bef)) + 1; } IT Pre(IT it) { return it == s.begin() ? s.end() : --it; } void Insert(const VEC& p) { if (relation(p)) return; bool del = false; VEC d; if (it != s.end() && it->x == p.x) { d = *it; del = true; s.erase(it); } it = s.insert(p).first; auto pre = Pre(it); auto nxt(it); ++nxt; if (pre != s.end()) { if (del) { area2 -= *pre ^ d; } else if (nxt != s.end()) { area2 -= *pre ^ *nxt; } area2 += *pre ^ p; for (auto j = Pre(pre); j != s.end() && ((*pre - p) ^ (*j - p)) >= 0; pre = j, j = Pre(j)) { area2 += (*j ^ p) - (*j ^ *pre) - (*pre ^ p); s.erase(pre); } } if (nxt != s.end()) { if (del) { area2 -= d ^ *nxt; } area2 += p ^ *nxt; auto j = nxt; for (++j; j != s.end() && ((*j - p) ^ (*nxt - p)) >= 0; nxt = j, ++j) { area2 += (p ^ *j) - (p ^ *nxt) - (*nxt ^ *j); s.erase(nxt); } } } }; struct ConvexHull { HalfConvexHull<down_sgn> down; HalfConvexHull<up_sgn> up; void Insert(const VEC& p) { down.Insert(p); up.Insert(p); } LT area2() const { if (down.s.empty()) return 0; return (*up.s.rbegin() ^ *down.s.begin()) + down.area2 + (*down.s.rbegin() ^ *up.s.begin()) + up.area2; } }; int main() { ConvexHull conv; VEC p; ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n = 3; while (n--) { p.input(); conv.Insert(p); } cin >> n; while (n--) { if (0 == n) { n = n * 2 / 2; } p.input(); conv.Insert(p); cout << conv.area2() << endl; } return 0; }