蓝桥杯2020年第十一届省赛真题-I题-平面切分详细注释

原题链接

2873. 平面切分 - AcWing题库https://www.acwing.com/problem/content/description/2876/代码

#include
#include //stl:set容器头文件引用  set不能添加已经存在的元素
using namespace std;
typedef pair pdd;  //typedef可以将一种数据类型定义为自己习惯的名称。
set line; //pair可以将两个数据合并成一个数据保存。这里将直线的斜率和截距作为一个数据保存，表示一条直线。
pdd iter; //存两直线焦点
int res = 1;
void compute(double x, double y)
{
	set points;//焦点集
	for (auto l = line.begin(); l != line.end(); l++) //遍历已经存在的直线，计算它们和(x,y)直线的焦点
	{
		double a = l->first;
		double b = l->second;
		if (a != x)//不平行 则肯定相交
		{
			iter.first = (b - y) / (x - a);//计算焦点x
			iter.second = iter.first *x + y;//计算焦点y
			points.insert(iter);//存储焦点
		}
	}
	res += points.size();//有几条焦点，就加几
}
int main()
{
	int n; cin >> n;
	while (n--)
	{
		double k, b;
		cin >> k >> b;
		int m = line.size();
		line.insert(make_pair(k, b)); 
		if (m != line.size())//如果能够添加该直线，说明该直线未出现过
		{
			res++;//如果该直线不和任意直线相交，划分的平面只加1， 再与其他直线有k个交点，就再加k(通过compute函数来计算)
			compute(k, b);//计算该直线与已经存在的直线的交点个数
		}
	}
	cout << res << endl;
}