BZOJ1132: [POI2008]Tro(叉积 排序)

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN = 3001;
int N;
struct Point {
    int a, b;
    Point operator - (const Point &rhs) const {
        return (Point) {a - rhs.a, b - rhs.b};
    }
    bool operator < (const Point &rhs) const {
        return a * rhs.b > rhs.a * b;
    }
}p[MAXN], tmp[MAXN];
bool comp(const Point &aa, const Point &bb) {
    return aa.a == bb.a ? aa.b < bb.b : aa.a < bb.a;
}
int main() {
    N; scanf("%d", &N);
    for(int i = 1; i <= N; i++) 
        scanf("%lf %lf", &p[i].a, &p[i].b);
    sort(p + 1, p + N + 1, comp);
    memcpy(tmp, p , sizeof(p));
    long double ans = 0;
    for(int i = 1; i <= N; i++) {
        for(int j = i + 1; j <= N; j++) p[j] = p[j] - p[i];
        sort(p + i + 1, p + N + 1);
        double suma = 0, sumb = 0;
        for(int j = N; j > i; j--) 
            suma = suma + p[j + 1].a, sumb = sumb + p[j + 1].b,
            ans = ans + p[j].a * sumb - p[j].b * suma;
        memcpy(p, tmp, sizeof(tmp));
    }
    printf("%.1Lf", ans / 2);
    return 0;
}