第十一届蓝桥杯C/C++B组省赛-平面切分

题目

题目链接

题解

计算几何。

存在这么一个结论：

向一个平面中加入一条直线，分两种情况，

1. 若新加入的直线不与平面中的任何一条直线重合，则向平面中加入该直线对平面部分数的贡献为：平面中已经存在的直线与该直线相交得到的不同的交点数 + 1；

2. 若新加入的直线与平面中的某条直线重合，则该直线没有贡献.

特别地，当平面中没有直线时，平面部分数为 1。

举几个例子：

代码

#include<bits/stdc++.h>
#define PDD pair <long double, long double> 
using namespace std;

const int N = 1010;

int n, ans;
long double a[N], b[N]; // 开 long double 
bool vis[N];

int main()
{
	cin >> n;
	for (int i = 1;i <= n;i ++) {
		cin >> a[i] >> b[i];
		set <PDD> s;
		s.clear ();
		for (int j = 1;j < i;j ++) {
			if (vis[j]) continue; // 如果枚举到的j是重合直线，直接跳过了，因为在j之前肯定存在与之一样的直线 
			if (a[i] == a[j] && b[i] == b[j]) { // 第i条直线的斜率与截距与前i-1条直线中的某一条完全一致说明重合 
				vis[i] = true; // 标记第i条直线是一条重合直线 
				break; // 重合无贡献，交点不算，直接break 
			}
			if (a[i] == a[j]) continue; // 如果第i条直线与当前枚举到的第j条直线平行，则说明i和j直线无交点，直接continue，不用向set中加入交点 
			s.insert ({ (b[i]-b[j])/(a[j]-a[i]), (a[j]*b[i]-a[i]*b[j])/(a[j]-a[i]) }); // 交点的计算是采用的行列式的方式计算的，克拉默法则了解一下 
		}
		if (!vis[i]) ans += s.size () + 1; // 只有当第i条直线不是重合直线时才统计 
	}
	cout << ans + 1 << endl; // 初始平面的1 
	return 0;
}