题目链接：[USACO16DEC] Lots of Triangles P

萌萌计算几何题。

如图，我们过三角形的三个顶点分别作垂直于 $x$ 轴的直线，我们可以发现，三角形 $=$ 大直角梯形 $-$ 两个小直角梯形。而两点确定一个这样的梯形。我们枚举梯形是 $O\left(n^2\right)$ 的。

判断一个点是否在梯形内部，只要判断一个点横坐标是否在该梯形两个底边之间，并且是否在斜线下方。

因此我们可以 $O\left(n^3\right)$ 求出一个梯形包含的点数。

然后我们就可以 $O\left(1\right)$ 求出每个三角形包含的点数。

总时间复杂度 $O\left(n^3\right)$。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

int read()
{
	int f = 1;
	char c = getchar();
	while (!isdigit(c))
	{
	    if (c == '-') f = -1;
	    c = getchar();
    }
	int x = 0;
	while (isdigit(c))
	{
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}

int buf[15];

void write(int x)
{
	int p = 0;
	if (x < 0)
	{
	    putchar('-');
	    x = -x;
	}
	if (x == 0) putchar('0');
	else
	{
		while (x)
		{
			buf[++p] = x % 10;
			x /= 10;
		}
		for (int i = p; i >= 1; i--)
			putchar('0' + buf[i]);
	}
}

const double eps = 1e-18;

int n, x[305], y[305], ans[305], cnt[305][305];

bool down(int x1, int y1, int x2, int y2, int x3, int y3)
{
	double k, b;
	k = (y2 - y1) * 1.0 / (x2 - x1);
	b = y1 * 1.0 - x1 * 1.0 * k;
	if (x3 * k + b - y3 > eps) return 1;
	return 0;
}

signed main()
{
	n = read();
	for (int i = 1; i <= n; i++)
		x[i] = read(), y[i] = read();
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
		{
			int x1 = x[i], y1 = y[i], x2 = x[j], y2 = y[j];
			if (x1 > x2)
			{
				swap(x1, x2);
				swap(y1, y2);
			}
			for (int k = 1; k <= n; k++)
			{
				if (k == i || k == j) continue;
				if (x[k] > x1 && x[k] <= x2) 
				{
					cnt[i][j] += down(x1, y1, x2, y2, x[k], y[k]); 
					cnt[j][i] += down(x1, y1, x2, y2, x[k], y[k]);
				}
			}
		}
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
		{
			int x1 = x[i], y1 = y[i], x2 = x[j], y2 = y[j];
			if (x1 > x2)
			{
				swap(x1, x2);
				swap(y1, y2);
			}
			for (int k = 1; k <= n; k++)
			{
				if (k == i || k == j) continue;
				if (x[k] > x1 && x[k] <= x2 && down(x1, y1, x2, y2, x[k], y[k]))
				{
					int tot = cnt[i][j] - cnt[i][k] - cnt[j][k] - 1;
					ans[tot]++;
				}
				if (x[k] >= x1 && x[k] < x2 && !down(x1, y1, x2, y2, x[k], y[k]))
				{
					int tot = cnt[i][k] + cnt[j][k] - cnt[i][j];
					ans[tot]++;
				}
			}
		}
	for (int i = 0; i <= n - 3; i++)
	{
		write(ans[i]);
		putchar('\n');
	}
	return 0;
}