自动搬运

查看原文

来自洛谷，原作者为

	FZzzz **

搬运于2025-08-24 21:49:23，当前版本为作者最后更新于2019-09-07 14:18:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

似乎其他两篇题解都说得不太清楚的样子，那我写一篇好懂一点的吧。

首先使用assert，测出$n\le3000$。

我们考虑三个点$A$，$B$，$C$组成的三角形面积，根据叉积的几何意义可知$S_{\triangle ABC}=\frac{|(x_B-x_A)(y_C-y_A)-(x_C-x_A)(y_B-y_A)|}{2}$，整理得$S_{\triangle ABC}=\frac{|x_A(y_B-y_C)+y_A(x_C-x_B)+x_By_C-x_Cy_B|}{2}$。

那我们为了不暴力统计，考虑依次固定一个点，比如$A$点。

但这就产生一个问题：如果其他点相对$A$的极角跨度超过$180^\circ$的话，绝对值无法消去，不好处理。所以我们将所有点按照纵坐标从小到大排序，然后依次考虑。每次考虑时，把后面所有点复制一下，按照极角再排一次序。这样只要$C$排在$B$后面，绝对值就可以去掉。

然后我们依次考虑所有点作为点$B$。可以发现只要知道后面所有点的坐标之和，就能一次算出所有三角形面积和。所以我们从后往前扫描$B$点，维护后缀和即可。

总时间复杂度为$n^2\log n$。代码如下：

#include<iostream>
#include<algorithm>
#include<cctype>
#include<cstdio>
using namespace std;
typedef long long ll;
inline ll readint(){
	ll x=0;
	char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)){
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
struct Point{
	ll x,y;
	Point(int x=0,int y=0):x(x),y(y){}
};
typedef Point Vector;
inline Point readpoint(){
	Point p;
	p.x=readint();
	p.y=readint();
	return p;
}
Vector operator -(Vector a,Vector b){
	return Vector(a.x-b.x,a.y-b.y);
}
inline ll cross(Vector a,Vector b){
	return a.x*b.y-b.x*a.y;
}
int n;
const int maxn=3000+5;
Point p[maxn];
bool cmp1(Point a,Point b){
	return a.y<b.y||(a.y==b.y&&a.x<b.x);
}
Point p2[maxn];
Point aa;
bool cmp2(Point a,Point b){
	return cross(a-aa,b-aa)>0;
}
ll ans=0;
int main(){
	#ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    n=readint();
    for(int i=0;i<n;i++) p[i]=readpoint();
    sort(p,p+n,cmp1);
    for(int i=0;i<n;i++){
    	aa=p[i];
    	for(int j=i+1;j<n;j++) p2[j]=p[j];
    	sort(p2+i+1,p2+n,cmp2);
    	ll sx=0,sy=0;
    	for(int j=n-1;j>i;j--){
    		ans+=aa.x*(p2[j].y*(n-j-1)-sy)+aa.y*(sx-p2[j].x*(n-j-1))+p2[j].x*sy-sx*p2[j].y;
    		sx+=p2[j].x;
    		sy+=p2[j].y;
		}
	}
	if(ans%2==1) cout<<ans/2<<".5"<<endl;
	else cout<<ans/2<<".0"<<endl;
    return 0;
}