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

题意

世上最良心题目描述qwq

Sol

直接模拟是$n^3$的。

考虑先枚举一个$i$，那么我们要算的就是$\sum_{j = 1}^n \sum_{k = j + 1}^n |Cross((a_j, b_j), (a_k, b_k))|$

但是在计算相对坐标以及叉积的时候的时候会出现绝对值

前者我们在最开始按照$x$坐标排序，后者在枚举$i$时重新按照斜率从小到大排序

上面的式子可以化为

$$\sum_{j = 1}^n a_j \sum_{k = j + 1}^n b_k - b_j \sum_{k = j + 1}^n a_k$$

直接对$a,b$做后缀和即可

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int MAXN = ;

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 = ; i <= N; i++)

        scanf("%lf %lf", &p[i].a, &p[i].b);

    sort(p + , p + N + , comp);

    memcpy(tmp, p , sizeof(p));

    long double ans = ;

    for(int i = ; i <= N; i++) {

        for(int j = i + ; j <= N; j++) p[j] = p[j] - p[i];

        sort(p + i + , p + N + );

        double suma = , sumb = ;

        for(int j = N; j > i; j--)

            suma = suma + p[j + ].a, sumb = sumb + p[j + ].b,

            ans = ans + p[j].a * sumb - p[j].b * suma;

        memcpy(p, tmp, sizeof(tmp));

    }

    printf("%.1Lf", ans / );

    return ;

}