计算几何入门——极角排序【数三角形】

题目源自$usaco2010open$usaco2010open

???AC代码样例输出竟是3???

推荐题解

注：

• $atan2(y,x)$atan2(y,x)所表达的意思是坐标原点为起点，指向$(x,y)$(x,y)的射线在坐标平面上与$x$x轴正方向之间的角的角度（$cmath$cmath里）
• $r=r$r=r%$n+1$n+1不是$r=(r+1)$r=(r+1)%$n$n
• 开$longlong$longlong
• 每次计算完$cnt$cnt只用建减一，$r$r不用变，因为跳到下一个节点是只有它自己减少了，原来的都不变

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct point{
	long long x,y;
	double k;
}a[N];
long long operator *(const point &c,const point &d){//叉积 
	return c.x*d.y-c.y*d.x;
}
int n;
bool cmp(const point &c,const point &d){
	return c.k<d.k;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&a[i].x,&a[i].y);
		a[i].k=atan2(a[i].y,a[i].x);
		//atan2(y,x)所表达的意思是坐标原点为起点，指向(x,y)的射线在坐标平面上与x轴正方向之间的角的角度。
	}
	sort(a+1,a+n+1,cmp);
	int r=2,cnt=0;
	long long ans=0;
	for(int i=1;i<=n;i++){
		while(r!=i&&a[i]*a[r]>=0){r=r%n+1;cnt++;}//
		ans+=(long long)cnt*(cnt-1)/2;
		cnt--;//
	}
	printf("%lld",(long long)n*(n-1)*(n-2)/6-ans);
	return 0;
}