蓝桥杯 平面切分【第十一届】【省赛】【B组】c++题解

平面上有 N 条直线，其中第 i 条直线是 y=Ai⋅x+Bi。

请计算这些直线将平面分成了几个部分。

输入格式

第一行包含一个整数 N。

以下N行，每行包含两个整数 Ai,Bi。

输出格式

一个整数代表答案。

样例输入

3
1 1
2 2
3 3

Data

样例输出

6

Data

评测用例规模与约定

对于 50 的评测用例，1≤N≤4, −10≤Ai,Bi≤10。

对于所有评测用例，1≤N≤1000, −100000≤Ai,Bi≤100000。

思路：【1】初始一条直线时有两个部分，后逐渐增加直线，计算每次当前直线与前面的所有直线的交点数，然后增加（交点数+1）个部分

【2】用set去存放直线以及交点，前者是防止重合的直线多次计算，后者是防止重合的交点多次计算

#include
#include
#include
using namespace std;
typedef long double ld;
set< pair >s;//记录直线
set< pair >p;//记录交点
ld a[1005], b[1005];//在去除重合的直线后，记录Ai和Bi，方便后面用于计算
int main() {

	int n, sum, i, j;
	ld x, y, A, B;
	cin >> n;
	for (int i1 = 1; i1 <= n; i1++)
	{
		cin >> A >> B;
		s.insert(make_pair(A, B));
	}
	n = s.size();
	set< pair >::iterator it;
	for (i = 0, it = s.begin(); it != s.end(); i++, it++)
	{
		a[i] = (*it).first;
		b[i] = (*it).second;
	}
	sum = 2;//第一条直线已经有2个部分
	for (i = 1; i < n; i++)//从第二条直线开始判断每一条直线与前面的所有线是平行还是相交
	{
		for (j = i - 1; j >= 0; j--)//枚举第i条直线前面的所有直线
		{
			if (a[j] == a[i])continue;//平行无交点
			//通过结合y=a[i]x+b[i]和y=a[j]x+b[j]可得
			x = (b[j] - b[i]) / (a[i] - a[j]);
			y = (a[j] * b[i] - a[i] * b[j]) / (a[j] - a[i]);
			p.insert(make_pair(x, y));//防止交于同一个点
		}
		sum += (p.size() + 1);//0个交点一样加1
		p.clear();
	}
	cout << sum;
	return 0;
	system("pause");
}