Problem
给定平面上 $n$ 个点,问有多少个三角形使得原点在三角形内部
原点不在任意两个点的连线上
Thought
首先按照极角排序
极角排序可以先按象限比较,再按叉积比较,这样不会有精度问题
当然直接用 $atan2$ 也是可以的
然后枚举一个点 $(x,y)$ 作为起始点,将所有在直线$(0,0),(x,y)$ 右侧的点加入队列中
发现队列中的点和 $(x,y)$ 任意组合形成的三角形必然不会过原点
所以就这样减去所有不包含原点的三角形即可
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double eps = 1e-8;
const int N = 100010;
struct Vector {
double x, y;
Vector operator + (const Vector a) const {return Vector{x + a.x, y + a.y};}
Vector operator - (const Vector a) const {return Vector{x - a.x, y - a.y};}
Vector operator * (const double a) const {return Vector{x * a, y * a};}
double operator * (const Vector a) const {return x * a.y - y * a.x;}
}v[N];
queue <Vector> q;
int n;
bool cmp(Vector a, Vector b) {
double t1 = atan2(a.y, a.x);
double t2 = atan2(b.y, b.x);
if(t1 < 0) t1 += pi * 2;
if(t2 < 0) t2 += pi * 2;
return t1 - t2 <= eps;
}
int main() {
scanf("%d", &n);
long long ans = 1ll * n * (n - 1) * (n - 2) / 2 / 3;
for(int i = 1; i <= n; ++ i)
scanf("%lf %lf", &v[i].x, &v[i].y);
sort(v + 1, v + n + 1, cmp);
for(int i = 2; i <= n; ++ i)
q.push(v[i]);
int num = n - 1;
for(int i = 1; i <= n; ++ i) {
while(v[i] * q.front() >= 0) {
q.pop();
-- num;
}
ans -= 1ll * num * (num - 1) / 2;
q.push(v[i]);
++ num;
}
printf("%lld\n", ans);
return 0;
}