問題概要

N個の点 $ (x_i,y_i) $ が与えられる。四点と、それらを結んでできる四角形に内包される点の組の総数を求めよ。ただし四点の順番は区別しない。
制約
$N\le 2500$
$x _ i ,y _ i \le 10 ^ 9$

考察

$ N ^ 2 \log N$ が間に合うので中心の点を固定したときに四点の組の数が $N \log N$ くらいで求められれればよい。
次に四点 $ A , B , C ,D $ が中心の点を包含する条件を考える。
中心を端点とした $A $ を通る線分上で $A$ を動かしても、包含関係は変わらない。　
なので、偏角にのみ注目すればよいことがわかる。
偏角がある180度の範囲に含まれているとき、すなわちある中心を通る直線に対して $A,B,C,D$ がすべて同じ側にある時 $ABCD$ は中心の点を包含しない。また、これは必要十分である。

実装方針

各点ごとに残りの $N-1$ 点を偏角ソートし、条件を満たさない組の数を数え、全体から引く。　　条件を満たさないような四点の組はそのうち反時計周りで最初のもので数えることにすれば重複しない。　　 1点を決め、反時計周りに $180$ 度以内にある点の数を求めていけばよい。　　計算量は $O( N ^2 \log N ) $ 。

ソースコード

#include<bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<n;i++)
#define pb push_back
#define all(c) begin(c),end(c)
using namespace std;

struct point{
    int x,y;
    bool operator<(const point &r)const{
        int lx = x , ly = y,
        rx = r.x , ry = r.y;
        if(ly == 0){
            if(lx>0) lx=INT_MAX,ly=1;
            else lx=-INT_MAX,ly=-1;
        }
        if(ry == 0){
            if(rx > 0) rx=INT_MAX,ry=1;
            else rx=-INT_MAX,ry=-1;
        }
        if(ly < 0 && ry > 0) return false;
        if(ly > 0 && ry < 0) return true;
        if(ly > 0){
            if(lx >= 0 && rx < 0)return true;
            if(lx <0 && rx >= 0)return false;
            return (ll)ly*rx < (ll)lx*ry;
        }
        else{
            if(lx >= 0 && rx < 0)return false;
            if(lx <0 && rx >= 0)return true;
            return (ll)ly*rx < (ll)lx*ry;
        }
    }
};

using points = vector<point>;

main(){
    ll n; cin>>n;
    points v;
    rep(i,n){
        int x,y; cin>>x>>y;
        v.pb(point{x,y});
    }
    ll ans=n*(n-1)/2*(n-2)/3*(n-3)/4*(n-4);
    rep(i,n){
        int x=v[i].x,y=v[i].y;
        points now;
        rep(j,n){
            if(i!=j)now.pb(point{v[j].x-x,v[j].y-y});
        }
        sort(all(now));
        rep(j,n-1){
            point a={-now[j].x,-now[j].y};
            ll s=lower_bound(all(now),a)-now.begin();
            if(s<=j)s+=n-1;
            s-=j+1;
            ans-=s*(s-1)*(s-2)/6;
        }
    }
    cout<<ans<<endl; 
}