「Bzoj 1132」「POI2008」Tro (计算几何, 叉积求三角形面积+极角排序)

Bzoj 1132
题意：平面上有$N$个点. 求出所有以这$N$个点为顶点的三角形的面积和

已知平面3点$A,B,C$, 求三角形面积：$S=|(y_b-y_a)(x_c-x_a)-(y_c-y_a)(x_b-x_a)|$

我们可以让$A$变为坐标原点，那么$S=|y_bx_c-y_cx_b|$

那么我们可以把点按$x$坐标排序，然后枚举点$i$, 考虑$i$右边的点对答案贡献

我们发现上式像叉积并且三角形面积有向性，我们可以把右边点极角排序，然后就能确定符号了，那么直接倒序枚举$j \in (i, n]$，用个前缀和处理$k$即可

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 5000 + 5;

    struct point {
        int x, y;
        point operator - (const point &rhs) const {return (point){x - rhs.x, y - rhs.y};}
        bool operator < (const point &rhs) const {return x == rhs.x ? y < rhs.y : x < rhs.x;}
    }a[MAXN], b[MAXN];
    bool cmp(point a, point b) {return b.x * a.y < b.y * a.x;}    

    int n;
    LL ans;

    void clean() {
    }
    int solve() {

        clean();
        cin >> n;
        for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i].x, &a[i].y);
        sort(a + 1, a + 1 + n);

        for (int i = 1; i <= n; ++i) {
            int tot = 0;
            for (int j = i + 1; j <= n; ++j) b[j] = a[j] - a[i];
            sort(b + 1 + i, b + 1 + n, cmp);
            LL sx = 0, sy = 0;
            for (int j = n; j > i; --j) {
                ans += b[j].x * sy - b[j].y * sx;
                sx += b[j].x, sy += b[j].y;
            }
        }

        printf("%lld.%lld\n", ans / 2ll, ans % 2ll * 5ll);

        return 0;
    }  
}
int main() {
    flyinthesky::solve();
    return 0;
}