平面切分- 蓝桥杯第十届Python组第十题

概述题目大意给定多条直线，询问这多条直线将平面分成了几部分？输入A和B，代表当前直线为y=A*X+B思路我们知道一条直线可以把平面分成两部分，可以理解成这条直线的加入贡献了一个新的部分（可能说的不严谨，指的是答案加1，因为初始状态是一个整的平面）若用ci[i]表示第i条加 题目大意

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

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

思路

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

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

易知ci[1] = 1

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

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

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

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

代码实现

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

import sysn = 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)        

总结

以上是内存溢出为你收集整理的平面切分- 蓝桥杯第十届Python组第十题全部内容，希望文章能够帮你解决平面切分- 蓝桥杯第十届Python组第十题所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。