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; }转载于:https://www.cnblogs.com/liu-runda/p/9280021.html
