https://www.luogu.org/problemnew/solution/P2992

考虑包含原点,不包含原点的三角形有什么特征.

包含原点的三角形:任意找一个顶点和原点连线,一定能把另外两个顶点隔开到两侧.

不包含原点的:三个顶点中只有一个顶点满足:和原点连线后,能把另外两个顶点隔开到两侧.

因此我们统计这样的三点组(x,y,z)的数目:x和原点的连线能把y和z隔开在两侧.

一共C(n,3)个三角形,包含原点的贡献3个三点组,不包含的只贡献1个.

统计三点组的数目只需要把所有点按照极角进行排序,然后枚举x.

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

struct point{

  int x,y;

  void read(){

    scanf("%d%d",&x,&y);

  }

  bool operator <(const point &B)const{

    return atan2(y,x)<atan2(B.y,B.x);

  }

}P[200005];

long long cross(point A,point B){

  return A.x*1ll*B.y-A.y*1ll*B.x;

}

int main(){

  int n;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){

    P[n+i]=P[i];

  }

  int j=1;

  long long cnt=0;

  for(int i=1;i<=n;++i){

    while(cross(P[i],P[j+1])>0)++j;

    cnt=cnt+(j-i)*1ll*(n-1-(j-i));

  }

  printf("%lld\n",(cnt-n*1ll*(n-1)*(n-2)/6)/2);

  return 0;

}