自动搬运

查看原文

来自洛谷，原作者为

	xtx1092515503 Mathematics compares the most diverse phenomena, and discovers the secret analogies which unite them. @Joseph Fourier

搬运于2025-08-24 21:44:11，当前版本为作者最后更新于2020-11-30 12:08:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

不需要容斥的做法。

---

我们考虑三个点构成的三角形包含原点，当且仅当其按照逆时针排序后，两两间夹角小于 $180^\circ$。

于是我们考虑将所有点按照极角排序，对于每个三角形，我们会在其三个点中最先在序列中出现的那一个处对其加以统计。

我们考虑用two-pointers预处理出来 $far_i$ 表示对于位置 $i$ 的点，排在其后面的所有点中第一个与其夹角 $\geq 180^\circ$ 的点是哪一个。则以 $i$ 作为第一个点的所有三角形，其第二个点 $j$ 必须 $\in(i,far_i)$，第三个点 $k$ 必须 $\in[far_i,n]$。

然后我们还发现，因为 $j,k$ 的夹角也必须 $<180^\circ$，所以 $k$ 的范围实际上是 $[far_i,far_j)$。

所以我们就要求出如上文所述的 $i,j,k$ 三元组数量。即

$$\sum\limits_{i=1}^n\sum\limits_{j=i+1}^{far_i-1}\sum\limits_{k=far_i}^{far_j-1} $$

于是

$$\sum\limits_{i=1}^n\sum\limits_{j=i+1}^{far_i-1}far_j-far_i $$

所以

$$\sum\limits_{i=1}^n\Big(\sum\limits_{j=i+1}^{far_i-1}far_j\Big)-(far_i-i-1)far_i $$

然后 $far_j$ 的区间和直接前缀和一下即可简单计算上式。

时间复杂度 $O(n\log n)$，瓶颈在于排序。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi=acos(-1);
ll res;
int n,far[100100];
ll sum[100100];
struct Vector{
	double x,y;
	Vector(){}
	Vector(double X,double Y){x=X,y=Y;}
	friend Vector operator +(const Vector &u,const Vector &v){return Vector(u.x+v.x,u.y+v.y);}
	friend Vector operator -(const Vector &u,const Vector &v){return Vector(u.x-v.x,u.y-v.y);}
	friend Vector operator *(const Vector &u,const double &v){return Vector(u.x*v,u.y*v);}
	friend Vector operator /(const Vector &u,const double &v){return Vector(u.x/v,u.y/v);}
	friend double operator &(const Vector &u,const Vector &v){return u.x*v.y-u.y*v.x;}//cross times
	friend double operator |(const Vector &u,const Vector &v){return u.x*v.x+u.y*v.y;}//point times
	double operator ~()const{return sqrt(x*x+y*y);}//the modulo of a vector
	double operator !()const{return atan2(y,x);}//the angle of a vector
	friend bool operator <(const Vector &u,const Vector &v){return !u<!v;}
	void read(){scanf("%lf%lf",&x,&y);}
	void print(){printf("(%lf,%lf)",x,y);}
}p[100100];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)p[i].read();
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++){
		far[i]=max(far[i-1],i);
		while(far[i]<=n&&!p[far[i]]-!p[i]<pi)far[i]++;
	}
	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+far[i];
	for(int i=1;i<=n;i++)res+=sum[far[i]-1]-sum[i-1]-1ll*(far[i]-i)*far[i];
	printf("%lld\n",res);
	return 0;
}