AcWing 2873. 平面切分(Python3)
原题链接
困难
作者:
跂未
,
2024-03-31 15:45:50
,
所有人可见
,
阅读 3
# 当直线不相交时,每增加一条直线平面的部分都会加1
# 当直线产生交点时,每多一个交点平面的部分就会多加1个(在不相交的基础上加)
# 所以在解题时,只要新加入的直线与已有的直线不重合,平面的部分就先加1。
# 再计算新加入的直线与已有的直线的交点个数,再加上该个数
# 求此条直线与其他所有直线的交点个数
def check(lines, a, b):
pnt = set()
for (c, d) in lines:
# 可能存在新加入的直线与多条直线交于一个点,那么只算一个点
# 我们将交点的坐标(x,y)求出来去重,防止一个点在一条直线上加多次
# 如果新加入的直线与其他直线的交点,新直线加入前就已经存在,
# 则该交点也算是新直线的交点
if a != c:
x = (b - d) / (a - c)
y = a * x + b
pnt.add((x, y))
return len(pnt)
n = int(input())
lines = set()
ans = 1
for _ in range(n):
a, b = map(int, input().split())
count = len(lines)
lines.add((a, b))
# 如果新加入的直线不重复
if len(lines) != count:
ans += 1
ans += check(lines, a, b)
print(ans)