C++11(clang++ 3.9) 解法, 执行用时: 380ms, 内存消耗: 872K, 提交时间: 2020-06-06 20:01:59

#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i <  _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;

const int N = 305;

int n;

struct P {
	ll x, y;
	P(ll _x = 0, ll _y = 0) {
		x = _x, y = _y;
	}
};

P a[N];

P operator - (P a, P b) { return P(a.x - b.x, a.y - b.y);}

int count(P a, P b, P c) {
	if(b.x == 0) return 0;
	if(b.x > 0) {
		if(c.x <= a.x || c.x > a.x + b.x) return 0;
		return b.x * c.y < (c.x - a.x) * b.y + a.y * b.x;
	} else {
		if(c.x > a.x || c.x <= a.x + b.x) return 0;
		return -(b.x * c.y > (c.x - a.x) * b.y + a.y * b.x);
	}
}

int c[N][N];

#define db double

db qj(P a) { return atan2(a.y, a.x);} 

db jd[N];
int d[N], d0;

int cmpd(int x, int y) { return jd[x] < jd[y];}

const db pi = acos(-1);

int calc(int x, int y, int z) {
	int s = c[x][y] + c[y][z] + c[z][x];
	s -= count(a[x], a[y] - a[x], a[z]);
	s -= count(a[y], a[z] - a[y], a[x]);
	s -= count(a[z], a[x] - a[z], a[y]);
	return abs(s);
}

ll C(ll n, ll m) {
	ll s = 1;
	fo(i, n - m + 1, n) s *= i;
	fo(i, 1, m) s /= i;
	return s;
}

int main() {
//	freopen("a.in", "r", stdin);
	scanf("%d", &n);
	fo(i, 1, n) {
		scanf("%lld %lld", &a[i].x, &a[i].y);
	}
	fo(i, 1, n) {
		fo(j, 1, n) if(i != j) {
			P p = a[i], q = a[j] - a[i];
			fo(k, 1, n) c[i][j] += count(p, q, a[k]);
		}
	}
	ll ans1 = 0, ans2 = 0;
	fo(i, 1, n) {
		d0 = 0;
		fo(j, 1, n) if(i != j) {
			jd[j] = qj(a[j] - a[i]);
			d[++ d0] = j;
		}
		sort(d + 1, d + d0 + 1, cmpd);
		fo(j, 1, d0) fo(k, j + 1, d0) {
			int x = d[j], y = d[k];
			ll w = k - j - 1;
			if(jd[y] - jd[x] > pi) w = d0 - 2 - w;
			ll w2 = calc(i, x, y);
			ans1 += w - w2;
			ans2 += (ll) w2 * (n - 3 - w2);
		}
	}
	ans1 /= 4; ans2 /= 3;
	ll ans = C(n, 3) * C(n - 3, 2);
	ans1 = ans1 * (n - 4) * 2;
	ans1 += ans2;
	ans1 /= 2;
	pp("%lld\n", ans - ans1);
}