平面切分- 蓝桥杯第十一届Python组第九题_平面切分摘要

题目大意

给定多条直线，询问这多条直线将平面分成了几部分？

输入 A 和 B，代表当前直线为y = A * X + B

思路

1. 我们知道一条直线可以把平面分成两部分，可以理解成这条直线的加入贡献了一个新的部分（可能说的不严谨，指的是答案加1，因为初始状态是一个整的平面）

2. 若用ci[i]表示第i条加入的直线对答案的贡献

3. 易知ci[1] = 1

4. 若当前加入直线与平面内现存直线存在n个不同交点，则ci[i] = 1 + n

5. 所以最终答案即为ci数组之和

那么ci[i]为什么等于1 + n呢？

简单思考下，第一条加入的直线势必会把平面分成两部分，第二条加入直线如果与第一条平行，那么这条直线只是在分割前面那两部分中的一部分，它不会对另一部分产生影响，如下图所示，用红色矩形表示整平面，则橙色直线不会对紫色区域产生分割。若不平行，那肯定会对紫色区域进行分割。

代码实现

注意要维护新加入直线与先前直线 不同的交点， 用set即可

import sys
n = int(input())
lines = []
for i in range(n):
    a, b = list(map(int, input().split()))
    lines.append((a, b))
lines = list(set(lines))#这里是去掉重复直线
n = len(lines)
def getnode(lines1, lines2):#得到两条直线交点，若平行，返回None
    A1 = lines1[0]
    B1 = lines1[1]
    A2 = lines2[0]
    B2 = lines2[1]
    if A1 - A2 == 0:
        return 
    x = (B2 - B1) / (A1 - A2)
    y = A1 * x + B1
    x = round(x, 10)
    y = round(y, 10)
    return (x, y)
ci = [1] * (n + 1)
node = set()
for i in range(1, n):
    node.clear()
    for j in range(i):
        tmp = getnode(lines[i], lines[j])
        if tmp == None: continue
        node.add(tmp)
    ci[i] += len(node)
        
print(sum(ci[:n]) + 1)        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31