文档章节

数学:平面分割直线

pricker
 pricker
发布于 2015/09/07 11:00
字数 574
阅读 199
收藏 0

我们看到过很多直线分割平面的题目,今天的这个题目稍微有些变化,我们要求的是n条折线分割平面的最大数目。比如,一条折线可以将平面分成两部分,两条折线最多可以将平面分成7部分,具体如下所示。
杭电acm2050 <wbr>折线分割平面

Input

输入数据的第一行是一个整数C,表示测试实例的个数,然后是C 行数据,每行包含一个整数n(0<n<=10000),表示折线的数量。

Output

对于每个测试实例,请输出平面的最大分割数,每个实例的输出占一行。

Sample Input

2
1
2

Sample Output

2
7

分析:

先看N条相交的直线最多能把平面分割成多少块

杭电acm2050 <wbr>折线分割平面

当添加第N条只显示,为了使平面最多, 则第N条直线要与前面的N-1条直线都相交,且没有任何三条直线教育一个点。

则第N条直线有N-1个交点。由于每增加N个交点,就增加N+1个平面,所以用N条直线来分隔平面,最多的数是1+1+2+3++n=1+n*(n+1)/2;

 

再看每次增加两条相互平行的直线

  杭电acm2050 <wbr>折线分割平面

 

当第N次添加时,前面已经有2N-2条直线了,所以第N次添加时,第2N-1条直线和第2N条直线都各能增加2*n-1+1 个平面。

所以第N次添加增加的面数是2[2(n-1) + 1] = 4n - 2 个。因此,总面数应该是

1 + 4n(n+1)/2 - 2n = 2n2 + 1 

 

如果把每次加进来的平行边让它们一头相交

杭电acm2050 <wbr>折线分割平面

则平面13已经合为一个面,因此,每一组平行线相交后,就会较少一个面,

所以所求就是平行线分割平面数减去N,为2n2 -n + 1

利用上述总结公式f(n)=2n2 -n + 1

#include<stdio.h>

int main()

{

int T,n;

scanf("%d",&T);

while(T--&&scanf("%d",&n)!=EOF)

printf("%d\n",2*n*n-n+1);

return 0;

}

或者利用公式f(n)=f(n-1)+4*n-1+1

#include<stdio.h>

int main()

{

__int64 s[10001]; 

    int i,T,n;

scanf("%d",&T);

while(T--)

{

s[0]=1;

scanf("%d",&n);

for(i=1;i<=n;i++)

s[i]=s[i-1]+4*(i-1)+1;

prin

本文转载自:http://blog.sina.com.cn/s/blog_76eabc150100swg8.html

pricker
粉丝 7
博文 56
码字总数 33145
作品 0
渭南
私信 提问
以图像分割为例浅谈支持向量机(SVM)

1. 什么是支持向量机?   在机器学习中,分类问题是一种非常常见也非常重要的问题。常见的分类方法有决策树、聚类方法、贝叶斯分类等等。举一个常见的分类的例子。如下图1所示,在平面直角坐...

lyrichu
2017/07/23
0
0
中文文本相似度---项目实践

由于下定决心开始攻克机器学习。辗转反侧,又是折腾线性代数,又是折腾概率论。然后又看了大学时候的高等数学。弄了大半天。不过今天还好有了收获,把思路进行罗列出来,与大家分享。 数学知...

Galy_绿
2016/07/31
28
0
支持向量机简介

一、回忆一些线性代数和几何 维空间中的一个仿射集是一个向量集。令的秩为。如果某,则该仿射集是所有满足的。它是维空间中的一个平面。如果某,且(的两行线性独立),则须满足方程组。若该...

张觉非
2016/07/13
0
0
支持向量机基本原理及在基因数据中的实践

这是一个梗,懂的人才能get到笑点 关于这个同学举牌子的典故我知道,我也是CMU的。这是在2009年在Pittsburgh举行的G20峰会现场外面。很多反对G20的,支持G20的都来凑热闹。我们这位同学也来了...

真依然很拉风
2017/07/29
0
0
为什么你的教学,学生总是提不起兴趣?

常言道:“兴趣是最好的老师。”有了兴趣,就会给学习带来激情和推动力,它促使学生对未知领域不断探索和研究。然而,有一部分学生对学习了无兴趣,不认真听讲,作业马虎,甚至旷课逃学,与老...

学术研究软件
2016/11/09
6
0

没有更多内容

加载失败,请刷新页面

加载更多

JWT学习总结

官方 https://jwt.io 英文原版 https://www.ietf.org/rfc/rfc7519.txt 或 https://tools.ietf.org/html/rfc7519 中文翻译 https://www.jianshu.com/p/10f5161dd9df 1. 概述 JSON Web Token(......

冷基
今天
4
0
AOP的学习(1)

AOP 理解AOP编程思想(面向方法、面向切面) spring AOP的概念 方面 -- 功能 目标 -- 原有方法 通知 -- 对原有方法增强的方法 连接点 -- 可以用来连接通知的地方(方法) 切入点 -- 将用来插入...

太猪-YJ
今天
4
0
一张图看懂亮度、明度、光度、光亮度、明亮度

亮度、明度、光亮度,Luminance和Brightness、lightness其实都是一个意思,只是起名字太难了。 提出一个颜色模型后,由于明度的取值与别人的不同,为了表示区别所以就另想一个词而已。 因此在...

linsk1998
昨天
11
0
Python应用:python链表示例

前言 python链表应用源码示例,需要用到python os模块方法、函数和类的应用。 首先,先简单的来了解下什么是链表?链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是...

python小白1
昨天
5
0
Source Insight加载源码

Source Insight是一个图形化的源代码查看工具(当然也可以作为编译工具)。如果一个项目的源代码较多,此工具可以很方便地查找到源代码自建的依赖关系。 1.创建工程 下图为Snort源代码的文件...

天王盖地虎626
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部