题意简介

题目就一句话：给出 $n$ 个在第一象限内（包括坐标轴）的整点，求其构成的所有三角形的面积之和。

思路描述

第一次看到这道题，立马想到枚举三个点 $i,j,k$，由这三个点构成的三角形面积 $S=\frac{1}{2}\left|x_1y_2+x_2y_3+x_3y_1-y_1x_2-y_2x_3-y_3x_1\right|$，每次只要把面积加在一起就可以了。
时间复杂度就是枚举的 $O(n^3)$，一般的题目最多只有 40 分左右，但是这题竟然能拿 84 分（代码略）。

如何优化呢？

最先发现的就是代码里的绝对值，它对优化很不利，应该想办法把它去掉。在什么时候绝对值可以去掉呢？也就是说，在三个点满足什么关系时，可以去掉绝对值？

可以画个图感受一下：

假设三个点的坐标分别为 $(1,1)$ $(2,3)$ 和 $(3,2)$。
在左图中，若按标号记三个点，则 $S=\frac{1}{2}|-3|=\frac{3}{2}$；
在右图中，$S=\frac{1}{2}|3|=\frac{3}{2}$。

发现了吗？在上图中，若另外两点较最下方一点按逆时针排布，那么绝对值可以去掉。或者更精炼地说，在上半平面内，逆时针排布的叉积恒为非负。

所以，我们可以在计算每个三角形时，都保证第一个点在最下方，这样算出来的三角形本身就不用带绝对值。反过来说，枚举第一个点时，只计算两个点都在其上方的三角形。
接下来就很明确了，先枚举第一个点，接下来以这个点为原点，重新计算每个点相对于它的坐标，取在其上方的点，并逐一计算面积。
我们可以先将所有点按纵坐标从小到大排序，方便后面的枚举。

但是到这里，我们还是没有做出优化。

优化如下：
假设第一个点已经确定，在其上方一共有 $k$ 个点，那么总面积

$$\begin{aligned} S&=\frac{1}{2}\sum_{i=1}^k\sum_{j=i+1}^k (x_iy_j-y_ix_j)\\ &=\frac{1}{2}(\sum_{i=1}^k\sum_{j=i+1}^k x_iy_j-\sum_{i=1}^k\sum_{j=i+1}^ky_ix_j)\\ \end{aligned}$$

其中，每个点都按逆时针排布，$x_i,y_i,x_j,y_j$ 都是相对于第一个点的坐标。
显然，我们可以使用后缀和优化 $x_j$ 和 $y_j$，这样就可以把计算的时间压到 $O(n)$。
整体的时间复杂度就是 $O(n\times (n\log n+n))$，也就是 $O(n^2\log n)$，可以接受。

代码展示

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#define int long long // 别忘了！ 
using namespace std;
int n;
bool cmp_y(pair<int,int>A,pair<int,int>B){
	return A.second<B.second||(A.second==B.second&&A.first<B.first);
} 
bool cmp_angle(pair<int,int>A,pair<int,int>B){
	return A.second*B.first<A.first*B.second;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	vector<pair<int,int>>s(n);
	for(int i=0;i<n;i++){
		cin>>s[i].first>>s[i].second;
	}
	sort(s.begin(),s.end(),cmp_y); // 事先按纵坐标大小排序 
	int ans=0;
	for(int i=0;i<n;i++){
		vector<pair<int,int>>a;
		for(int j=i+1;j<n;j++){
			a.push_back({s[j].first-s[i].first,s[j].second-s[i].second}); // 计算相对坐标 
		}
		sort(a.begin(),a.end(),cmp_angle); // 枚举过程中按逆时针排序 
		int l=a.size();
		vector<int>sufx(l+1,0); // 对 x 后缀和
		vector<int>sufy(l+1,0); // 对 y 后缀和 
		for(int j=l-1;j>=0;j--){
			sufx[j]=sufx[j+1]+a[j].first;
		}
		for(int j=l-1;j>=0;j--){
			sufy[j]=sufy[j+1]+a[j].second;
		}
		for(int j=0;j<l;j++){
			ans+=a[j].first*sufy[j+1]-a[j].second*sufx[j+1]; // 计算叉积和 
		}
	}
	if(ans&1)cout<<(ans-1)/2<<".5"; // 这样写更保险 
	else cout<<ans/2<<".0";
}