【题解】BZOJ 1914 数三角形

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