蓝桥杯 平面切分 python组_蓝桥杯平面切分python

题目描述

平面上有 N 条直线，其中第 ii 条直线是y=Ai​*x+Bi​。

请计算这些直线将平面分成了几个部分。

输入描述

第一行包含一个整数 N。

以下 N 行，每行包含两个整数 Ai​,Bi​。

其中，1≤N≤1000,−10**5≤Ai​,Bi​≤10**5。

输出描述

一个整数代表答案。

解答：每增加一条直线，对平面数增加的贡献值，是其与先前直线的交点数（不包括与已有交点重合的点）+1。第一条直线把平面切分成两半，往后则是求该点与其前面的线的交点，count += 交点个数+1，遍历所有直线之后，最终结果则为count，输出即可。

N = int(input())

li = []

for i in range(N):

        D = [int(x) for x in input().split()]

        li.append((D[0],D[1])) #元组数据（k,b）

li = list(set(li)) #列表去重

#每增加一条直线，对平面数增加的贡献值，是其与先前直线的交点数（不包括与已有交点重合的点）+1

count = 2

for i in range(1,len(li)):#当前直线下标

        pli = set()#交点集

        for j in range(i):#先前直线下标

                k1 = li[i][0];b1 = li[i][1]

                k2 = li[j][0];b2 = li[j][1]

                if k1 == k2:#平行线无交点

                        continue

                x = (b1-b2)/(k2-k1)        #斜率

                y = k1*px+b1

                pli.add((x,y))        #set集合具有自动去重功能，所以不会有两条线斜率一样，并同时记录再pli数组中的情况，确保结果的正确性

        count += len(pli) + 1

print(count)