How Many Triangles (极角排序 + 尺取法)

　　题意：二维平面与有很多个点，然后求构成锐角三角形的个数。

　　思路：对于每一个三角形我们知道存在至少2个锐角，只要有一个钝角就不行了，所以我们的想法就是枚举所有夹角的状态，然后得知情况，确定用总个数减去-成线或者成钝角的数量/2(除以2是因为计算过程中重复了)。那么应该如何枚举？我们枚举夹角的顶点然后就出其他点的极角，排序，然后尺取法左端点表示与当前点为锐角的个数，右端点表示锐角+钝角，过程中相减可以得到锐角数量。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn =  + ;

struct P{

    ll x, y;

    P() {}

    P(ll x, ll y): x(x), y(y) {}

    P operator + (P p) {

        return P(x + p.x, y + p.y);

    }

    void read() {

        scanf("%lld%lld", &x, &y);

    }

    P operator - (P p) {

        return P(x - p.x, y - p.y);

    }

    ll dot(P p) {//点积

        return x * p.x + y * p.y;

    }

    ll det(P p) {//叉积

        return x * p.y - y * p.x;

    }

    bool operator < (const P &p) const{

        if(y * p.y <= ) {

            if(y >  || p.y > ) return y < p.y;

            if(y ==  && p.y == )return x < p.x;

        }

        return x * p.y - y * p.x > ;

    }

}p[maxn], q[maxn << ];

int main(){

    int n;while(~scanf("%d", &n)) {

        ll ans = 1ll * n * (n - ) * (n - ) / ;

        ll line = ;

        for(int i = ; i < n; i ++) p[i].read();

        for(int i = ; i < n; i ++) {

            int tot = ;

            for(int j = ; j < n; j ++)

                if(i != j) q[tot ++] = p[j] - p[i];

            ll subtrat = ;

            sort(q, q + tot);

            for(int j = ; j < tot; j ++) q[j + tot] = q[j];

            for(int j = ; j < tot; j ++) {

                if(q[j - ].det(q[j]) ==  && q[j - ].dot(q[j]) > ) subtrat ++;

                else subtrat = ;

                line += subtrat;

            }

            int l = , r = ;

            for(int j = ; j < tot; j ++) {

                while(l <= j || (l < j + tot && q[l].det(q[j]) <  && q[j].dot(q[l]) > )) l ++;

                while(r <= j || (r < j + tot && q[r].det(q[j]) < )) r ++;

                ans -= r - l;

            }

        }

        printf("%lld\n",ans - line/);

    }

    return ;

}