用整形实现的。封装好了。就是不知道为什么有点慢。
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;
operator + (const VEC& b) const {
VEC 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;
}
operator - (const VEC& b) const {
VEC return VEC{x - b.x, y - b.y};
}
const {
LT len2() return sq(x) + sq(y);
}const VEC& b) const {
LT dist2(return (*this - b).len2();
}
//Might overflow
operator * (const VEC& b) const {
LT return x * b.x + y * b.y;
}operator ^ (const VEC& b) const {
LT 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;
}
const VEC& p1, const VEC& p2) const {
LT cross(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;
//to (0, 0)
LT area2;
IT it;0) {}
HalfConvexHull() : area2(//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;true;
del =
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);
}const {
LT area2() 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;
false);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(
int n = 3;
while (n--) {
p.input();
conv.Insert(p);
}
cin >> n;while (n--) {
if (0 == n) {
2 / 2;
n = n *
}
p.input();
conv.Insert(p);
cout << conv.area2() << endl;
}return 0;
}