精华内容
下载资源
问答
  • 多边形对角线交点个数

    千次阅读 2020-06-20 22:45:53
    因为每一个交点对应两条对角线,而两条对角线又对应着一个四边形.于是焦点个数就对应四边形的个数.问题转化成由凸n边形的n个顶点取4个顶点可组成多少个四边形的问题,故最多共有n(n-1)(n-2)(n-3)/24个交点. ...

    凸N边形的对角线条数为:n(n-3)/2
    因为每一个交点对应两条对角线,而两条对角线又对应着一个四边形.于是焦点个数就对应四边形的个数.问题转化成由凸n边形的n个顶点取4个顶点可组成多少个四边形的问题,故最多共有n(n-1)(n-2)(n-3)/24个交点.

    展开全文
  • 这是一道洛谷的原创题目,评论区中大部分都是用传统的排列组合方法来进行公式的推导,设有n个顶点,则只需要选出四个顶点,就能有一个交点,所以答案就是C(4,n)

    这是一道洛谷的原创题目,评论区中大部分都是用传统的排列组合方法来进行公式的推导,设有n个顶点,则只需要选出四个顶点,就能有一个交点,所以答案就是C(4,n)

    x = int(input())
    print ( x * ( x - 1 )// 2 * ( x - 2 ) // 3 * ( x - 3 ) // 4 )
    

    但是,如果没有这个公式,如何写代码呢?

    n=int(input())
    b=[]
    sum=0
    for i in range(1,n-1):
        for j in range(i+2,n+1):
            if j-i!=n-1:
                a=[i,j]
                b.append(a)
    for o in range(len(b)-1):
        k=b[o]
        for p in range(o+1,len(b)):
            l=b[p]
            if k[0]<l[0]<k[1] and k[1]<l[1]:
                sum+=1
    print(sum)
    

    该做法的思路为:

    首先,将该凸多边形的顶点依次标上序号,如六边形六个顶点依次为:1,2,3,4,5,6

    然后,选出能构成对角线的两个点的组合,构成一个二位列表,经过推断可知,构成对角线的条件为:

    1,两个数字的差不能为1,也就是两个点不能相邻。

    2,因为1号点与n号点也相邻,但是之间的差值却不是1,所以应该将这种情况排除。

    例:六边形经过第一次的筛选可以得到二维列表

    [[1, 3], [1, 4], [1, 5], [2, 4], [2, 5], [2, 6], [3, 5], [3, 6], [4, 6]]([1,3]代表点1和点3的连线)

    最后一步,我们应该寻找能构成焦点的两条线的关系,经过推导可知:

    对于两条对角线[a,b],[c,d]。(a<b,c<d)

    如果a<c<b<d或c<a<d<b

    即可构成一个交点

    展开全文
  • 有一个公式奇数的时候有作用的,我自己做的时候推,推不出来= =! c++的时候也wa了,估计是哪里没处理到位,还好有python n=input(); n= eval (n); n=n *n *n *n - 6 *n *n *n + 23 *n *n - 42 *n + 24 ;...

    题目描述
    Niuniu likes mathematics. He also likes drawing pictures. One day, he was trying to draw a regular polygon with n vertices. He connected every pair of the vertices by a straight line as well. He counted the number of regions inside the polygon after he completed his picture. He was wondering how to calculate the number of regions without the picture. Can you calculate the number of regions modulo 1000000007?It is guaranteed that n is odd.输入描述:The only line contains one odd number n(3 ≤ n ≤ 1000000000), which is the number of vertices.输出描述:Print a single line with one number, which is the answer modulo 1000000007.
    示例1
    输入复制
    3
    输出复制
    1
    示例2
    输入复制
    5
    输出复制
    11备注:
    The following picture shows the picture which is drawn by Niuniu when n=5. Note that no three diagonals share a point when n is odd.

    有一个公式是对奇数的时候有作用的,我自己做的时候推,推不出来= =!
    c++的时候也wa了,估计是哪里没处理到位,还好有python

    n=input();
    n=eval(n);
    n=n*n*n*n-6*n*n*n+23*n*n-42*n+24;
    n=n//24;
    n=n%1000000007;
    print(n);
    
    
    展开全文
  • N顶点凸多边形对角线交点的个数

    千次阅读 多人点赞 2020-02-28 11:02:47
    对于一个N个定点的凸多边形,他的任何三条对角线都不会交于一点。请求楚图形中对角线交点的个数。 例如,6边形: 我们可以发现,两条不平行对角线才会有一个交点,同时,两条对角线又确定了一个四边形,也就是确定...

    题目描述
    对于一个N个定点的凸多边形,他的任何三条对角线都不会交于一点。请求楚图形中对角线交点的个数。

    例如,6边形:
    在这里插入图片描述
    我们可以发现,两条不平行对角线才会有一个交点,同时,两条对角线又确定了一个四边形,也就是确定了4个顶点。如果我们确定了4个顶点的组合方式,我们也就能确定有多少个四边形,进而确定有多少个对角线交点。用排列组合的计算公式就是
    在这里插入图片描述
    即N*(N-1)(N-2)(N-3)/(4321)
    考虑到如果初始N很大时,上面结果会超级大,可以改写成N
    (N-1)/2*(N-2)*/3(N-3)/4

    那为什么这样一定是对的呢?难道不会因为除不尽却向下取整而导致错误吗?

    事实上是一定除得尽的

    首先n和n-1一定有一个是2的倍数,因此2可以除尽,

    同理n,n-1,n-2中一定有一个是3的倍数,因此3可以除尽(除掉2只会消除因数2而对3没有影响)

    同理4也可以除尽
    用C语言描述就是:

    #include<stdio.h>
    
    int main()
    {
    	unsigned long long n;
    	scanf("%lld",&n);
    	if(n<=3)
    		printf("0\n");
    	else
    		printf("%lld\n",n*(n-1)/2*(n-2)/3*(n-3)/4);
    	return 0;
    }
    
    
    

    (此代码在VC++6.0中无法运行,会出现error C2632: ‘long’ followed by ‘long’ is illegal
    原因:

    因为 VC6中所使用的编译器是C90标准的,而 long long 型是在C99中新加入的

    (longlong int双长整型是C 99扩充的数据类型,同时扩充的还有float_complex,double_complex,long

    long_complex,bool等),故无法实现编译。(——此答案搜索于百度)
    VisualC++6.0 环境运行下,将long long 用 _int64 进行替换,则输入输出的格式字符串应该写成%I64d以输入输出long long类型的整数。)

    在这里插入图片描述

    展开全文
  • 有趣的对角线公式

    2019-01-25 11:52:00
    SUM(N(OFFSET($A$ 1 ,ROW($ 1 : 1 )- 1 ,ROW()-ROW($ ...第一个是左上开始计算, ...第三个是右上反向计算(从最长边计算到顶点)   转载于:https://www.cnblogs.com/LcxSummer/p/10318830.html
  • 对于一个 n 个顶点的凸多边形,它的任何三条对角线都不会交于一点。请求出图形中对角线交点的个数。 例如,6 边形: 这里可以注意到并没有出现多条对角线交叉在一个点的情况。 输入格式 输入只有一行一个整数 n,...
  • 题目:对一个凸多边形,通过若干条不相交的对角线,把这个凸多边形剖分成若干个三角形,输入多边形边数n,输出不同剖分方案数。当n=5时,方案数为5递推公式:C(n)=(4*n-10)/(n-1)*C(n-1) (我也不会推....)#include ...
  • 洛谷P2181 对角线

    2021-02-17 11:36:15
    对于一个 n 个顶点的凸多边形,它的任何三条对角线都不会交于一点。请求出图形中对角线交点的个数。 输入格式 输入只有一行一个整数 n,代表边数。 输出格式 输出一行一个整数代表答案。 输入输出样例 输入 #1 3 ...
  • 洛谷P2181——对角线

    2018-11-15 20:38:33
    对于一个N个定点的凸多边形,他的任何三条对角线都不会交于一点。请求楚图形中对角线交点的个数。 例如,6边形: 输入输出格式 输入格式: 第一行一个n,代表边数。 输出格式: 第一行输出交点数量   ...
  • P2181 对角线

    2021-02-27 18:27:08
    对于一个N个定点的凸多边形,他的任何三条对角线都不会交于一点。请求楚图形中对角线交点的个数。 例如,6边形: 题解: 首先由于不会有三条对角线交于一点,所以过某一个交点有且只能有2条对角线 而这两条对角线...
  • 文章目录数学计算思路n凸边形对角线交点公示例题展示 数学计算思路 == 两条线确定一个交点(该问题中不存在三条线交...题目:对于一个 n 个顶点的凸多边形,它的任何三条对角线都不会交于一点。请求出图形中对角线交点
  • 洛谷 P2181 对角线

    千次阅读 2020-06-28 10:58:33
    对于一个 nn 个顶点的凸多边形,它的任何三条对角线都不会交于一点。请求出图形中对角线交点的个数。 例如,66 边形: #组合数学 #数据处理技巧 观察之后可以发现,每两条对角线可以确定一个交点,同时联系起四个...
  • n凸边行的对角线交点个数

    千次阅读 2018-11-15 20:48:28
    首先由于不会有三条对角线交于一点,所以过某一个交点有且只能有2条对角线。 两条对角线实质上是确定了4个顶点,四个顶点构成一个四边形,所以问题就转换为求四边形的数量。 然而我们只需要确定4个顶点就得到了...
  • n边形对角线交点问题

    千次阅读 2020-06-30 15:38:12
    对于一个n个顶点的凸多边形,其任三条对角线都不会相交于一点,求对角线交点个数 我们知道四边形的对角线交点个数只有一个,所以该题转化成为求这个n边形有多少个四边形。n个顶点,有顺序的任取4个顶点,用组合数...
  • 1361:对角线的数量

    2020-10-27 15:43:38
    数学上规定多边形对角线是不相邻的两个顶点之间的线段。求正n边形对角线的数量。 输入 多组案例。一个正整数n,表示案例的数量。(n<=20) 每组案例由一个正整数m组成,表示m边形。(3<=m<=100万) 输出 ...
  • luogu 2182对角线

    2018-05-17 19:39:22
    对于一个N个定点的凸多边形,他的任何三条对角线都不会交于一点。请求楚图形中对角线交点的个数。 输入输出格式 输入格式: 第一行一个n,代表边数。 输出格式: 第一行输出交点数量 输入输出样例 输入样例#1...
  • 对于一个 n 个顶点的凸多边形,它的任何三条对角线都不会交于一点。请求出图形中对角线交点的个数。 例如,6 边形: 输入格式 输入只有一行一个整数 nn,代表边数。 输出格式 输出一行一个整数代表答案。 输入输出...
  • 对于一个 nn 个顶点的凸多边形,它的任何三条对角线都不会交于一点。请求出图形中对角线交点的个数。 例如,66 边形: 输入格式 输入只有一行一个整数 nn,代表边数。 输出格式 输出一行一个整数代表答案。 输入...
  • 对于一个 n 个顶点的凸多边形,它的任何三条对角线都不会交于一点。请求出图形中对角线交点的个数。 例如,6 边形: 输入格式 输入只有一行一个整数 n,代表边数。 输出格式 输出一行一个整数代表答案。 输入...
  • 对于一个 nn 个顶点的凸多边形,它的任何三条对角线都不会交于一点。请求出图形中对角线交点的个数。 例如,6 边形: 输入格式 输入只有一行一个整数 nn,代表边数。 输出格式 输出一行一个整数代表答案。 输入...
  • 对于一个N个定点的凸多边形,他的任何三条对角线都不会交于一点。请求楚图形中对角线交点的个数。 例如,6边形: 输入输出格式 输入格式: 第一行一个n,代表边数。 输出格式: 第一行输出交点数量 ...
  • 对于一个 nnn 个顶点的凸多边形,它的任何三条对角线都不会交于一点。请求出图形中对角线交点的个数。 例如,666 边形: 输入格式 输入只有一行一个整数 nnn,代表边数。 输出格式 输出一行一个整数代表答案。 输入...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,956
精华内容 2,782
关键字:

多边形的对角线公式