[蓝桥杯2020初赛] 平面切分

题目

题目描述
平面上有N 条直线，其中第i 条直线是y = Ai * x + Bi。
请计算这些直线将平面分成了几个部分。
输入格式
第一行包含一个整数N。
以下N 行，每行包含两个整数Ai, Bi。
对于50% 的评测用例，1 ≤ N ≤ 4, -10 ≤ Ai, Bi ≤ 10。
对于所有评测用例，1 ≤ N ≤ 1000, -100000 ≤ Ai, Bi ≤ 100000。
输出格式
一个整数代表答案。
输入样例 复制
3
1 1
2 2
3 3
输出样例 复制
6

分析

这道题目首先我们得知道一个数学小常识：在同一个平面内，如果添加一条直线，与平面所有的直线不相交，则会增加一个平面，如果与这个平面内的一条直线相交并且产生不同的位置的交点，那么就会额外增加一个平面。
那么我们在做题的过程中，只需判断是否时重边，计算新增加的直线与前面的直线有多少个不同的交点，重边非常的好判断，直接用一个数组标记一下即可，计算交点我们也可以用set（可以自动去重）。

参考代码

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_map>
#define LL long long
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define reps(i, a, b) for(int i = a; i < b; i++) 
#define pre(i, a, b) for(int i = b; i >= a; i--)
using namespace std;

const int N = 1010;
typedef pair<double, double> PDD;

bool st[N]; //用来标记重边，防止重复计算交点
double a[N][2];

int main()
{
    
	int n;
	cin >> n;
	
	int ans = 1; // 一开始有一个平面
	rep(i, 1, n)
	{
    
		cin >> a[i][0] >> a[i][1];
		set<PDD> point; // 计算该直线与平面内的直线的不同交点的个数
		
		rep(j, 1, i - 1)
		{
    
			if(st[j]) continue;
			if(a[i][0] == a[j][0])
			{
    
				if(a[i][1] == a[j][1]) 
				{
    
					st[i] = true;
					break;
				}
				
				else continue;
			}
			
			double x = (a[i][1] - a[j][1]) / (a[j][0] - a[i][0]);
			double y = a[i][0] * x + a[i][1];
			point.insert({
    x, y});
		}
		
		if(!st[i]) ans += point.size() + 1;
	}
	
	cout << ans << endl;
	return 0;
}