第十一届蓝桥杯省赛第二场真题（python组）——平面切分（注释详细）

试题 I: 平面切分
时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分
【问题描述】
平面上有 N 条直线，其中第 i 条直线是 y = Ai · x + Bi。
请计算这些直线将平面分成了几个部分。
【输入格式】
第一行包含一个整数 N。
以下 N 行，每行包含两个整数 Ai, Bi。
【输出格式】
一个整数代表答案。
【样例输入】
3
1 1
2 2
3 3
【样例输出】
6
【评测用例规模与约定】
对于 50% 的评测用例，1 ≤ N ≤ 4, 10 ≤ Ai, Bi ≤ 10。
对于所有评测用例，1 ≤ N ≤ 1000, 100000 ≤ Ai, Bi ≤ 100000。

解题思路：
我们知道没有直线的时候，平面只有一个
当有一条直线的时候，平面被分成两部分
当有两条直线的时候，这时有三种情况：平行，重合，相交
平行的话平面分成三部分（没有不同的交点）
重合的话平面分成两部分（无意义的一步）
相交的话平面分成四部分（有一个不同的交点）
当有三条直线的时候，新加入的直线和之前的两条直线也有三种情况：平行 重合 相交
平行的话平面在之前基础上划分平面数量加1（没有交点）
重合（无意义，等于啥也没干）
相交的话
如果和两者都于相交一个点（之前基础基础上分成部分数量加1+1）
如果和两者相交不同的两个点(之前基础基础上分成部分数量加1+2)

在这里我们可以找到规律了，每次新加入的线段如果和之前的线段有n个不同的交点，就在原来的基础上多分出n+1个平面

N=int(input())
input_lis=[]
crosspoint_x_set=set()	#使用set便于去重，这样通过set长度计算不同点的个数
each_line_num_lis = [1] * (N + 1)
for i in range(N):
    input_lis.append(list(map(int,input().split())))
for i in range(1,N):
	'每次在空间上加入一条线段'
    crosspoint_x_set.clear()#crosspoint_x_set计算的第n条直线与前面直线的交点x，我们只需要的是set的长度，算出长度之后作为N加，然后clear，继续计算下一个条直线与前面直线的交点x
    for n in range(i):
    	'计算新加入的线段与之前线段的交点'
        if input_lis[i-n-1][0]!=input_lis[i][0]:	#重合的时候直接不用计算
            x=round((input_lis[i][1]-input_lis[i-n-1][1])/(input_lis[i-n-1][0]-input_lis[i][0]),4) #交点x坐标
            crosspoint_x_set.add(x)
    each_line_num_lis[i] += len(crosspoint_x_set)	#每算出一个就在原来1的基础上加n
print(sum(each_line_num_lis) ) 

个人总结：这道题目感觉有点像找规律的题目，由于时间和空间的限制，我们必须想办法在尽量少使用遍历的情况下完成题目。