ZOJ 3871 Convex Hull | 计算几何、凸包

• double atan2(double y,double x) 返回的是原点至点(x,y)的方位角，即与 x 轴的夹角。返回值的单位为弧度，取值范围为（-π, π]。结果为正表示从 X 轴逆时针旋转的角度，结果为负表示从 X 轴顺时针旋转的角度。
• 理解多边形求面积的方法

题意：
给n个点，|x[i]|，|y[i]| <= 1e9。求在所有情况下的子集下（子集点数>=3），凸包的面积和。
分析：

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 998244353;
const int maxn = 1e3 + 10;
const int inf = 0x3f3f3f3f;
const double pi = 4 * atan(1);
struct point
{
    ll x, y;
    double angle;
    point(ll a = 0, ll b = 0, double c = 0) : x(a), y(b), angle(c){}
    bool operator< (const point& b)
    {
        return angle < b.angle;
    }
    point operator -(const point& b)
    {
        return point(x - b.x, y - b.y);
    }
    ll operator * (const point& b)
    {
        return x * b.y - y * b.x;
    }
}a[maxn], b[maxn << 1];
ll p[maxn];
int n;

void make()
{
    p[0] = 1;
    for(int i = 1; i < maxn; i++) p[i] = p[i - 1] * 2 % mod;
    for(int i = 0; i < maxn; i++) p[i] = (p[i] - 1 + mod) % mod;
}

int main()
{
    int t; cin >> t;
    make();
    while(t--)
    {
        cin >> n;
        for(int i = 1; i <= n; i++)
            cin >> a[i].x >> a[i].y;
        ll res = 0;
        for(int i = 1; i <= n; i++)
        {
            int tot = 0;
            for(int j = 1; j <= n; j++)
            {
                if(i == j) continue;
                b[++tot] = a[j];
                b[tot].angle = atan2(a[j].y - a[i].y, a[j].x - a[i].x);
            }
            for(int k = 1; k <= tot; k++) b[k + tot] = b[k], b[k + tot].angle = b[k].angle + 2.0 * pi; //后面的需要用到前面的
            sort(b + 1, b + 1 + tot + tot);
            int l = 1, r = 1;
            for(; l <= tot; l++)
            {
                while(b[r + 1].angle - b[l].angle < pi) r++;
                res = (res + ((a[i].x * b[l].y - a[i].y * b[l].x) % mod + mod) % mod * p[r - l] % mod) % mod;
            }
        }
        cout << res << endl;
    }
}