【每日一题】备战冲击蓝桥杯国赛——Python程序设计 | Day10 | 平面切分 | 真题代码解析

举报
府学路18号车神 发表于 2022/03/04 16:50:00 2022/03/04
【摘要】 今天是2020年省赛的最后一题,大家加油啊!~每天刷一道题,话不多说,先刷近两年的题吧,从2020的开始,如果有一起的可以加入我们!!!一起来刷题,冲击国赛!!! 2020年第十一届蓝桥杯赛题总览2020年的题就是这些,类型分为两种,分别是结果填空和程序设计,我们每天刷一道题,省赛没问题! 平面切分(题目)(本题总分:25分)官方练习系统:https://www.lanqiao.cn/pro...

今天是2020年省赛的最后一题,大家加油啊!~

每天刷一道题,话不多说,先刷近两年的题吧,从2020的开始,如果有一起的可以加入我们!!!

一起来刷题,冲击国赛!!!


2020年第十一届蓝桥杯赛题总览

2020年的题就是这些,类型分为两种,分别是结果填空和程序设计,我们每天刷一道题,省赛没问题!
在这里插入图片描述

平面切分(题目)

(本题总分:25分)

官方练习系统:https://www.lanqiao.cn/problems/505/learning/


—>【问题描述】

平面上有N条直线,其中第 i i 条直线是 y = A i × x + B i y=A_i×x+B_i

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

—>【输入描述】

第一行包含一个整数 N N

以下 N N 行,每行包含两个整数 A i , B i A_i,B_i

其中, 1 N 1000 1 0 5 A i , B i 1 0 5 1\le N\le 1000,-10^5\le A_i,B_i\le10^5

—>【输出描述】

输出一个整数,表示答案。

—>【输入输出样例】

输入:
3
1 1
2 2
3 3

输出:
6


解析


通过阅读题干,本题——难度中上:⭐⭐⭐⭐

考察类型:计算几何、思维

考察知识点:map(),max()


分析:

本道题其实算一道数学题,从输入输出描述来看,输入的是直线描述公式的a和b的值,我们可以简单的在草稿上绘制以下,如下:
在这里插入图片描述
由于是鼠标绘制,大家忍耐亿下下,三条直线将整个二维平面划分为了6个区间。

到这里我们大概理解了整个题目的意思,难点在于,我们如何将直线交叉的地方进行划分,最后得出划分的区域。思考一下!
算了,就不墨迹了。
我们从二元一次方程中可以得到的信息有限,是否可以看出某种规律来?在比赛的时候总不能手动去画吧。
面对N个二元一次方程,工科生第一想到的应该就是解方程。是否能够找到一个公共的交点,或者说多个交点呢。从示例的三个方程,一眼能看出有一个交点——(-1,0)。
我们再从一条直线到多条直线看看可以切分多少个平面:

  • 1条直线——2平面
  • 2条直线——2平面(重叠)、3平面(平行、无交点)、4平面(1个交点)
  • 3条直线——2、3平面(重叠)、4平面(平行、无交点)、6平面(1交点、2交点)、7平面(3交点)
  • 4条直线——2、3、4平面(重叠)、5平面(平行、无交点)、7平面(3交点,有两条线重叠)、8平面(3交点)、9平面(4交点)、10平面(4交点、5交点)

下面就不再列举了,从上面的列举我们可以看出一些规律法则。

  • N条直线,可以切分出N种数量的平面,根据不同的切分方式,N条直线的N种数量平面可以有和无交点,但也要考虑重叠的时候。由此,我们可以根据有无交点的数量来判断N条直线的平面切分数。
  • N条直线,我们知道A和B,首先计算出二元一次函数的交点数(这个不难),然后根据法则判断出交点数对应的切割平面数,即最终的结果。
    法则:
  1. 加入平面的直线所分割的平面数:直线与之前直线不重复交点数+1
  2. 直线如果有重叠的,需要去除重叠的
  3. 与不同直线的相同交点只计算一次

下面直接开干!!!


代码

Python代码实现:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2022/3/4 15:19
# @Author  : 府学路18号车神
# @Email   :yurz_control@163.com
# @File    : Day10.py

n = int(input("输入平面上直线的条数:"))
# 首先去除重叠的直线
lines = set(tuple(map(int, input("输入每条直线的A和B的值:").split())) for i in range(n))
n = len(lines)
new_lines = list(lines)


# 规则
def get_area(n, lines):
    p = 2   # 设置判断条件,一条直线有两个平面
    if n == 1:      # 出口
        return p
    for x in range(1, n):
        point = set()
        for y in range(x):
            # 当直线的斜率不同的时候才会出现交叉的时候(在本题中的A就是斜率K),由此我们计算不重复交点数
            if lines[x][0] != lines[y][0]:
                i = (lines[x][1]-lines[y][1])/(lines[y][0]-lines[x][0])     # 判断两直线是否存在交点
                j = (lines[x][0]*lines[y][1]-lines[x][1]*lines[y][0])/(lines[x][0]-lines[y][0])
                point.add((i, j))
        p += len(point)+1   # 添加计算的不重复交点数
    return p
print(get_area(n, new_lines))

示例1:
在这里插入图片描述

今天最后一题,稍有难度,加油!

由此,我们可以快速得出结果,验证完毕!

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。