极角排序

先开始想了很多分割方法，发现都不对，最后觉得只能极角搞搞，就看了答案

我们发现，一个点的原点构成的直线把平面分成了两半，那么只由一边点和这个点构成的三角形肯定不包含原点，那么我们按极角排序，然后计算右边有多少点C(x,2)就行了。因为一个三角形有三个点，枚举到中间那个点的时候这个三角形不会被计算，而如果两边都计算的话就会算重两次，于是我们只计算在右边的三角形就不会重负和遗漏了

极角排序就是计算atan2(y,x),计算出和x轴的弧度夹角，按这个排序就行了

#include
      
       using namespace std;const int N = 100010;const double pi = acos(-1);struct points {    double x, y, angle;    points(double x = 0, double y = 0, double angle = 0) : x(x), y(y), angle(angle) {}    bool friend operator < (points A, points B)    {        return A.angle < B.angle;    }} a[N];int n, cnt, pos;long long ans;inline long long Sum(long long x){    return x * (x - 1ll) * (x - 2ll) / 6ll;}inline long long calc(long long x){    return x * (x - 1ll) / 2ll;}inline double A(double x){    return x > 0 ? x : 2 * pi + x;}int main(){    scanf("%d", &n);    ans = Sum(n);    for(int i = 1; i <= n; ++i)    {        double x, y, angle;        scanf("%lf%lf", &x, &y);        angle = atan2(y, x);        if(angle < 0) angle += 2 * pi;        a[i] = points(x, y, angle);    }    sort(a + 1, a + n + 1);    for(int i = 2; i <= n; ++i) if(a[i].angle - a[1].angle > pi)     {        pos = i;        break;    }    cnt = pos - 1;    for(int i = 1; i <= n; ++i)    {        --cnt;        while(A(a[pos].angle - a[i].angle) < pi && pos != i)         {            ++pos;            pos = (pos - 1) % n + 1;            ++cnt;        }        ans -= calc(cnt);    }    printf("%lld\n", ans);    return 0;}