Description

对于一个平面上点的集合 \(P = \{(x_i, y_i)\}\), 定义集合 \(P\) 的面积 \(f(P)\) 为点集 \(P\) 的凸包的面积.

对于两个点集 \(A\) 和 \(B\), 定义集合的和为:

\[A + B = \{(x_i^A + x_j^B, y_i^B + y_j^B) | (x_i^A, y_i^A) \in A, (x_j^B, y_j^B) \in B\}\]

现在给定一个 \(n\) 个点的集合 \(A\) 和一个 \(m\) 个点的集合 \(B\), 求 \(2 \cdot f(A + B)\).

Input

第一行包含用空格隔开的两个整数, 分别为 \(n\) 和 \(m\);

第二行包含 \(n\) 个不同的数对, 表示 \(A\) 集合中的 \(n\) 个点的坐标;

第三行包含 \(m\) 个不同的数对, 表示 \(B\) 集合中的 \(m\) 个点的坐标.

Output

一共输出一行一个整数,\(2 \cdot f(A + B)\).

Sample Input

4 5
0 0 2 1 0 1 2 0
0 0 1 0 0 2 1 2 0 1

Sample Output

18

Source

2012 国家集训队 Round 1 day2

Explanation

对于 30% 的数据满足 \(n \leq 200, m \leq 200\);

对于 100% 的数据满足 \(n \leq 10^5, m \leq 10^5, 0 \leq |x_i|, |y_i| \leq 10^8\).

Explanation

首先这道题肯定要用凸包, 因为毕竟求的就是凸包==

然而我凸包并不会写, 只能参考别人的代码了, 多写几遍其实就好了 QwQ

但是有这样一个性质: 直接把 \(A+B\) 中点都求出来的是制杖, 因为最后集合的和的点并不 包括全部, 其实只是一个很小的子集. 更进一步地讲,\(A+B\) 凸包上某个点一定是 \(A\) 的凸包上的某个点加上 \(B\) 凸包上的某个点得到的. 这样只需要求两次凸包然后直接贪心 在 \(A\) 上绕一圈 \(B\) 的凸包就可以了. 具体地说, 这道题的复杂度有这样几个档次:

  1. \(O(n^2 m^2)\)
  2. \(O(nm \log (nm))\)
  3. \(O(n \log n + m \log m + \log (nm) \log \log (nm))\)
  4. \(O(n \log n + m \log m + \log (nm))\)

然后直接写第四种其实比前三种都好写的说...... (前提是你会)

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 500100;

class ConvexHull
{
public:
    struct point {
        lli x, y;
    };
    friend bool operator < (const point& a, const point& b)
    {
        if (a.x < b.x)
            return true;
        else if (a.x == b.x && a.y < b.y)
            return true;
        return false;
    }
    friend point operator + (const point& a, const point& b)
    {
        point c;
        c.x = a.x + b.x;
        c.y = a.y + b.y;
        return c;
    }
    friend point operator - (const point& a, const point& b)
    {
        point c;
        c.x = a.x - b.x;
        c.y = a.y - b.y;
        return c;
    }
    friend lli operator * (const point& a, const point& b)
    { // cross multiplication
        return a.x * b.y - b.x * a.y;
    }
    // The part of calculation of convex hulls
    int n;
    point arr[maxn], tmp[maxn];
    void eval(void)
    { // Returns n as the convex size, arr[] as the convex hull
        sort(arr + 1, arr + n + 1);
        int m = 0;
        for (int i = 1; i <= n; i++) {
            while (m > 1 && (arr[i] - tmp[m-1]) * (tmp[m] - tmp[m-1]) >= 0)
                m -= 1;
            tmp[++m] = arr[i];
        } int tm = m;
        for (int i = n-1; i >= 1; i--) {
            while (m > tm && (arr[i] - tmp[m-1]) * (tmp[m] - tmp[m-1]) >= 0)
                m -= 1;
            tmp[++m] = arr[i];
        } m -= 1;
        // Copying back to array.
        this->n = m;
        for (int i = 1; i <= m; i++)
            this->arr[i - 1] = this->tmp[i];
        return ;
    }
    lli get_area(void)
    {
        lli area = 0;
        for (int i = 2; i < n; i++)
            area += (arr[i] - arr[1]) * (arr[i+1] - arr[1]);
        return area;
    }
} A, B, T;

int n, m;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &A.arr[i].x, &A.arr[i].y);
    for (int i = 1; i <= m; i++)
        scanf("%lld%lld", &B.arr[i].x, &B.arr[i].y);
    A.n = n; B.n = m;
    A.eval();
    B.eval();
    // Calculating unified convex
    T.n = 0;
    T.arr[++T.n] = A.arr[0] + B.arr[0];
    for (int i = 0, j = 0; i < A.n || j < B.n; ) {
        ConvexHull::point
            x = A.arr[i % A.n] + B.arr[(j+1) % B.n],
            y = A.arr[(i+1) % A.n] + B.arr[j % B.n];
        if ((x - T.arr[T.n]) * (y - T.arr[T.n]) >= 0)
            T.arr[++T.n] = x, j++;
        else
            T.arr[++T.n] = y, i++;
    } T.n -= 1;
    // Calculating final area
    lli res = T.get_area();
    printf("%lld\n", res);
    return 0;
}