题解 P2992 【[USACO10OPEN]Triangle Counting G】

xtx1092515503 · 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 三元组数量。即

于是

所以

然后 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;
}