[蓝桥杯 2020 省 B2] 平面切分

题目描述

平面上有 N 条直线，其中第 i 条直线是 y = Ai · x + Bi。 请计算这些直线将平面分成了几个部分。

输入格式

第一行包含一个整数 N。 以下 N 行，每行包含两个整数 Ai; Bi。

输出格式

一个整数代表答案。

样例 #1

样例输入 #1

3
1 1
2 2
3 3

样例输出 #1

6

提示

对于 50% 的评测用例， 1 ≤ N ≤ 4, −10 ≤ Ai; Bi ≤ 10。 对于所有评测用例， 1 ≤ N ≤ 1000, −100000 ≤ Ai; Bi ≤ 100000。

蓝桥杯 2020 第二轮省赛 B 组 I 题

代码

思路 ：
在同一个平面内，如果添加的每一条直线互不相交，则每添加一条直线，就会增加一个平面；当添加一条直线时，这条直线与当前平面内已有直线每产生一个不同位置的交点时，这条直线对平面总数量的贡献会额外增多一个

#include<iostream>
#include<set>
using namespace std;

long double s[1010][2];
long long ans;
bool st[1010];
pair<long double, long double> p;


int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s[i][0] >> s[i][1];
		set<pair<long double, long double>> points;

		for (int j = 0; j < i; j++) {//依次比较 查找重边
			if (st[j])continue;//直线是重边
			if (s[i][0] == s[j][0]) {//斜率相同
				if (s[i][1] == s[j][1])
				{
					st[i] = true;
					break;
				}
				else continue;
			}
		p.first = (s[j][1] - s[i][1]) / (s[i][0] - s[j][0]);//交点的x坐标 
		p.second = s[i][0] * p.first + s[i][1];//交点的y坐标 
		points.insert(p);
		}
		if (!st[i])ans += points.size() + 1;//若不是重边，更新答案
	}
	cout << ans + 1;
}