[HOJ] 238 - Signaling

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<complex>
using namespace std;
#define N 1505
#define x real()
#define y imag()
typedef complex<double> P;
P s[N],in;
vector<P> arr;
double cross(P a,P b){
    return a.x*b.y-a.y*b.x;
}
int cmp(P p1,P p2){
    if(p1.y*p2.y>0)
        return p2.x*p1.y<p2.y*p1.x;
    else if(!p1.y){
        if(p1.x>0)
            return 1;
        return p2.y<0;
    }
    else if(!p2.y){
        if(p2.x>0)
            return 0;
        return p1.y>0;
    }
    return p1.y>0;
}
long long int C(long long int a,int b){
    if(a<b) return 0;
    if(b==3)
        return a*(a-1)*(a-2)/6;
    if(b==4)
        return a*(a-1)*(a-2)*(a-3)/24;
}
int n;
int main(){
    int i,j,k,L,R;
    long long int Q,P,X=0;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%lf%lf",&s[i].x,&s[i].y);
    for(i=0;i<n;i++){
        arr.clear();
        for(j=0;j<n;j++){
            if(j!=i){
                arr.push_back(s[j]-s[i]);
            }
        }
        sort(arr.begin(),arr.end(),cmp);
        for(j=0;j<n-1;j++)
            arr.push_back(arr[j]);
        for(L=0,R=1;L<n-1;L++){
            in=arr[L];
            while(cross(in,arr[R])>0 || R==L) R++;
            X+=(R-L-1)*(R-L-2)/2;
        }
    }
    P=C(n-1,3)*n-X;
    Q=C(n,4)*2-P;
    printf("%lf\n",double(Q)/C(n,3)+3);
}