【模板】二维计算几何初步

template <class T>
struct point {
    T x, y;
    point() : point(0, 0) {}
    point(T x, T y) : x(x), y(y) {}
    friend point operator+(const point &lhs, const point &rhs) {
        return { lhs.x + rhs.x, lhs.y + rhs.y };
    }
    friend point operator-(const point &lhs, const point &rhs) {
        return { lhs.x - rhs.x, lhs.y - rhs.y };
    }
    friend point operator*(const point &lhs, const T &k) {//数乘
        return { lhs.x * k, lhs.y * k };
    }
    friend T cross(const point &lhs, const point &rhs) {//叉积
        return lhs.x * rhs.y - rhs.x * lhs.y;
    }
    friend T operator*(const point &lhs, const point &rhs) {//向量内积
        return lhs.x * rhs.x + lhs.y * rhs.y;
    }
    friend T dist(const point &self) { return self * self; }//模长
    friend bool quad(const point &self) {//极角排序用于区分方向的象限（只判两个）
        return self.x <= 0 && self.y < 0 || self.x < 0 && self.y >= 0;
    }
    friend bool checkCross(const point &a, const point &b, const point &c, const point &d) {//两线段是否有交
        if (max(a.x, b.x) <= min(c.x, d.y) || max(c.x, d.x) <= min(a.x, b.x)) return 0;
        if (max(a.y, b.y) <= min(c.y, d.y) || max(c.y, d.y) <= min(a.y, b.y)) return 0;
        static const auto sgn = [&](const T &x) { return x == 0 ? 0 : (x < 0 ? -1 : 1); };
        return sgn(cross(a - c, d - c)) * sgn(cross(b - c, d - c)) < 0
            && sgn(cross(c - a, b - a)) * sgn(cross(d - a, b - a)) < 0;
    }
    friend bool operator==(const point &lhs, const point &rhs) {
        return lhs.x == rhs.x && lhs.y == rhs.y;
    }
    friend bool cmp(const point& a, const point& b) {
        return cross(a, b) ? cross(a, b) > 0 : dist(a) < dist(b);
    }
    friend bool operator<(const point& a,const point& b) {
        return a.x != b.x ? a.x < b.x : a.y < b.y;
    }
};
typedef point<LL> dot;
vector<dot> convexHull(vector<dot> a) {//凸包
    static dot stk[1 << 18];
    dot cen = *min_element(a.begin(), a.end());
    sort(a.begin(), a.end(),
        [&](const dot& a,const dot& b) { return cmp(a - cen, b - cen); });
    int top = 0;
    for (dot v: a){
        while (top >= 2 && cross(stk[top - 1] - stk[top], v - stk[top]) > 0)
            top--;
        stk[++top] = v;
    }
    return vector<dot>(stk + 1, stk + top + 1);
}
vector<dot> minkowski(const vector<dot>& a, const vector<dot>& b) {//闵可夫斯基和
    vector<dot> c = {a[0] + b[0]};
    static dot sa[1 << 18], sb[1 << 18];
    int n = a.size(), m = b.size();
    for (int i = 0; i < n; i++)
        sa[i] = a[(i + 1) % n] - a[i]; 
    for (int i = 0; i < m; i++)
        sb[i] = b[(i + 1) % m] - b[i]; 
    int i = 0, j = 0;
    for (int k = 1; k < n + m; k++){
        if (i < n && (j >= m || cmp(sa[i], sb[j])))
            c.push_back(c.back() + sa[i++]);
        else
            c.push_back(c.back() + sb[j++]);
    }
    return c;
}
bool checkIn(const vector<dot>& a, const dot& v) {//点是否在凸包内
    dot cen = a[0];
    if (cmp(a.back() - cen, v - cen))
        return 0;
    //if (cmp(v - cen, a[1] - cen)) return 0;
    if (cross(v - cen, a[1] - cen) ? cross(v - cen, a[1] - cen) > 0
                                   : dist(v - cen) > dist(a[1] - cen))
        return 0;
    auto p =
        lower_bound(a.begin() + 1, a.end(), v, [&](const dot& a,const dot& b) {
            return cmp(a - cen, b - cen);
        });
    return cross(*prev(p) - *p, v - *p) <= 0;
}