自动搬运

查看原文

来自洛谷，原作者为

	5ab_juruo May you find some comfort here

搬运于2025-08-24 21:51:44，当前版本为作者最后更新于2023-02-25 19:28:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

给一种不需要 set 的做法。

考虑数关键点之间的连线与多少个三角形相交。显然线段可以拆成两条射线答案的差，且射线的起点都是关键点。

同时注意到，当射线起点固定时，三角形的限制等价于极角的一段区间，代表这一段答案要加一。

枚举关键点作为射线起点，将所有要求的射线方向和三角形贡献的起点、终点按极角排序，扫描线即可。注意端点也要算进去。如果有跨越 $0,2\pi$ 的贡献，则可以拆成两段来算。

复杂度 $\mathcal{O}(n(n+m)\log(n+m))$。

const int max_n = 1000, max_m = 1000;

struct point
{
	int x, y;
	friend istream& operator>>(istream& is, point& p)
	{
		is >> p.x >> p.y;
		return is;
	}
	bool operator<(const point& rhs) const
	{
		if ((rhs.x > 0) ^ (x > 0))
			return x < rhs.x;
		return 1ll * y * rhs.x < 1ll * x * rhs.y;
	}
}
p[max_n], a[max_m], b[max_m], c[max_m];
vector<pair<point, int>> qc;
int f[max_n][max_n];

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m;
	
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> p[i];
	for (int i = 0; i < m; i++)
		cin >> a[i] >> b[i] >> c[i];
	qc.reserve(n + m * 3);
	
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		qc.clear();
		for (int j = 0; j < i; j++)
			qc.emplace_back(point{ 2 * p[i].x - p[j].x, 2 * p[i].y - p[j].y }, j);
		for (int j = i + 1; j < n; j++)
			qc.emplace_back(p[j], j);
		
		for (int j = 0; j < m; j++)
		{
			point x[3] = { a[j], b[j], c[j] };
			sort(x, x + 3, [&](point lhs, point rhs) {
				return 1ll * (rhs.y - p[i].y) * (lhs.x - p[i].x) > 1ll * (rhs.x - p[i].x) * (lhs.y - p[i].y);
			});
			if (point{ x[0].x - p[i].x, x[0].y - p[i].y } < point{ x[2].x - p[i].x, x[2].y - p[i].y })
			{
				qc.emplace_back(x[0], -1);
				qc.emplace_back(x[2], n);
			}
			else
			{
				qc.emplace_back(point{ p[i].x, int(2e8) }, -1);
				qc.emplace_back(x[2], n);
				qc.emplace_back(x[0], -1);
			}
		}
		
		for (auto &[pt, _] : qc)
			pt.x -= p[i].x, pt.y -= p[i].y;
		sort(qc.begin(), qc.end());
		
		int cnt = 0;
		for (auto [_, x] : qc)
		{
			if (x == -1)
				cnt++;
			else if (x == n)
				cnt--;
			else if (x < i)
				ans += (cnt == f[x][i]);
			else
				f[i][x] = cnt;
		}
	}
	
	cout << ans << endl;
	
	return 0;
}