题解 P2992 【[USACO10OPEN]Triangle Counting G】

不需要容斥的做法。 ------------ 我们考虑三个点构成的三角形包含原点，当且仅当其按照逆时针排序后，两两间夹角小于 $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)$，瓶颈在于排序。 代码： ```cpp #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; } ```