题目大意

二维平面上有一些点，保证不存在重合的点和三点共线。求每一个点集的凸包在平面上包含的点数的和。

$n\leq1000$ 。

题解

有趣的。

假如所有点都在所有凸包内，答案 $n2^n$ 。

考虑斥掉不合法的。对于一个点对，它们直线分割的半平面，两个平面内的点不能同时取。那么枚举一个点，把所有点挪到以它为原点的坐标系，然后极角排序，双指针维护半平面的区间即可。

本题的启发：如果有“不存在三点共线”的提示，可以考虑这种半平面的角度。

代码

const int N = 1010, mod = 1e9 + 7;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	struct Point {
		int x, y;
		Point(){}
		Point(int x, int y):x(x), y(y) {}
		friend bool operator < (Point a, Point b) { return atan2(a.y, a.x) < atan2(b.y, b.x); }
		friend Point operator + (Point a, Point b) { return Point(a.x + b.x, a.y + b.y); }
		friend Point operator - (Point a, Point b) { return Point(a.x - b.x, a.y - b.y); }
		friend ll operator * (Point a, Point b) { return 1ll * a.x * b.y - 1ll * b.x * a.y; }
	}a[N], b[N];
	int n;
	ll ans;
	ll p2[N];
	int main () {
		p2[0] = 1; for (int i = 1; i <= N - 10; i++) p2[i] = 2ll * p2[i - 1] % mod;
		n = Read();
		for (int i = 1; i <= n; i++) a[i].x = Read(), a[i].y = Read();

		ans = (p2[n] - 1) * n % mod;

		for (int i = 1; i <= n; i++) {
			int m = 0;
			for (int j = 1; j <= n; j++) if (i != j) b[m++] = a[j] - a[i];
			sort (b, b + m);
			for (int j = 0, cur = 0; j < m; j++) {
				for (; (cur + 1) % m != j && b[j] * b[(cur + 1) % m] > 0; cur = (cur + 1) % m);
				ans = (ans - p2[(cur - j + m) % m] + mod) % mod;
			}
		}
		printf ("%lld\n", ans);
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}