N顶点凸多边形中对角线交点的个数

article/2025/9/17 10:48:28

题目描述
对于一个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");elseprintf("%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类型的整数。)

在这里插入图片描述


http://chatgpt.dhexx.cn/article/goBoQ3iX.shtml

相关文章

凸多边形的划分

题目&#xff1a; 给定一个具有 NN 个顶点的凸多边形&#xff0c;将顶点从 11 至 NN 标号&#xff0c;每个顶点的权值都是一个正整数。 将这个凸多边形划分成 N−2N−2 个互不相交的三角形&#xff0c;对于每个三角形&#xff0c;其三个顶点的权值相乘都可得到一个权值乘积&a…

`算法知识` 多边形, 凸多边形, 外接矩形

catalog 图片引用图二 多边形分类周长多边形的外接矩形 凸多边形去除若干点, 仍为凸多边形 ID_COUNT: 3 图片引用 图二 多边形 以下讨论, 均在(笛卡尔坐标系)中, 即两点间的距离为 (欧几里得距离) 由N条边和N个点组成, N > 3, 面积一定> 0 每条边, 都是(线段) 线段: 必…

判断多边形的凹凸性和计算多边形面积:利用向量叉乘

根据百度百科的讲解&#xff1a; 凸多边形 现在重点讲解顶点凹凸性法&#xff08;最常用也是较为简单的方法&#xff09;&#xff1a;计算总结在最后。 利用向量叉乘的相关知识进行计算&#xff1a;假设当前连续的三个顶点分别是P1&#xff0c;P2&#xff0c;P3。计算向量P1P3…

判断点在凸多边形內

判断点在凸多边形內 判断点在凸多边形内的算法有很多&#xff0c;可以参考链接3&#xff0c;个人尝试使用了同侧法&#xff0c;此处也只解析这个方法 算法原理&#xff1a; 同侧法是判断点在向量哪一侧的一个方法&#xff0c;这个算法的概念是来自于参考文献一&#xff0c;参…

—【动态规划】凸多边形最优三角剖分

0014算法笔记——【动态规划】凸多边形最优三角剖分 分类&#xff1a; 算法 2013-03-05 20:10 612人阅读 评论(0) 收藏 举报 三角剖分 凸多边形最优解 动态规划 算法笔记 1、问题相关定义&#xff1a; (1)凸多边形的三角剖分&#xff1a;将凸多边形分割成互不相交的三角形的…

0014算法笔记——【动态规划】凸多边形最优三角剖分

1、问题相关定义&#xff1a; (1)凸多边形的三角剖分&#xff1a;将凸多边形分割成互不相交的三角形的弦的集合T。 (2)最优剖分&#xff1a;给定凸多边形P&#xff0c;以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分&#xff0c;使得该三角…

判断平面多边形的凹凸性

对于平面多边形的三角化处理也是计算机图形学里面的一个领域&#xff0c;最近由于项目的需要&#xff0c;需要对平面多边形进行剖分&#xff0c;特此对其作了些研究。 在对平面多边形进行处理的时候&#xff0c;很多时候需要知道多边形的凹凸性&#xff0c;本文介绍两种方法来…

最小凸多边形(凸包)

描述 给出平面上n个点的坐标&#xff0c;计算最远两点间的距离&#xff0c;以及包含所有点的最小凸多边形&#xff08;凸包&#xff09; 输入 第一行一个整数n&#xff0c;接下来是n行的实数对&#xff0c;表示n个点坐标。2<n<10000 n x1 y1 x2 y2 … xn yn 输出 输出…

计算机几何 - 如何判断一个多边形是凸多边形还是凹多边形

什么是凸多边形和凹多边形&#xff1f; 凸多边形&#xff1a;每个内角都是锐角或钝角&#xff0c;没有大于180度的内角(例如&#xff0c;三角形、正方形)。 凹多边形&#xff1a;至少有一个大于180度的内角(例如&#xff0c;五角星)。 注&#xff1a;大于180度的角又被称为优角…

多边形扩展和收缩(凸多边形和凹多边形)

目录 背景介绍&#xff1a;知识积累&#xff1a;思路点拨&#xff1a;代码区域&#xff1a; 背景介绍&#xff1a; 如下图所示&#xff0c;黑色是原多边形&#xff0c;红色是扩展的多边形&#xff0c;蓝色是收缩的多边形。这是最终的效果。 PS&#xff1a;楼主使用的是ES6的语…

什么是凸多边形和凹多边形

GIS有时需要用算法判断线段是否在多边形内&#xff1b; 最基本的出发点如下&#xff0c; 线段在多边形内的一个必要条件是线段的两个端点都在多边形内&#xff0c;但由于多边形可能为凹&#xff0c;所以这不能成为判断的充分条件&#xff1b; 就是说&#xff0c; 如果线段的两…

判断多边形是凹多边形还是凸多边形,以及求凹点

转载&#xff1a;计算机几何 - 如何判断一个多边形是凸多边形还是凹多边形_刘建宁的博客-CSDN博客_凹多边形和凸多边形的区别 重点&#xff1a; 1.凸多边形指的是多边形的每个内角小于180度。 2.凹多边形指的是至少有一个内角大于180度。 判断多边形性质 多边形内角和等于(n…

凸多边形最优三角

前言&#xff1a;大三下算法课&#xff0c;自己看的凸多边形最优三角&#xff0c;最后上台讲解&#xff0c;和子涵苗子等一起的一段时间 1.相关概念 • 凸多边形&#xff1a;一个简单多边形及其内部构成一个闭凸集时&#xff0c;则 称该简单多边形为一个凸多边形。 • 边&#…

动态规划DP——凸多边形最优三角剖分

1.问题分析 我们可以把披萨饼看作是一个凸多边形&#xff0c;凸多边形是指多边形的任意两点的连线均落在多边形的内部或边界上。 &#xff08;1&#xff09;什么是凸多边形&#xff1f; 如下图所示&#xff0c;是一个凸多边形 如下图所示&#xff0c;不是一个凸多边&#xff0c…

凸多边形、凹多边形、凸包算法

凸多边形&#xff1a; &#xff08;Convex Polygon&#xff09;可以有以下三种定义&#xff1a; 1、没有任何一个内角是优角&#xff08;Reflexive Angle&#xff09;的多边形。 2、如果把一个多边形的所有边中&#xff0c;有一条边向两方无限延长成为一直线时&#xff0c;其他…

搜狗浏览器屏蔽广告插件_“云法庭”里“云勘验” 法院开审搜狗浏览器插件屏蔽优酷视频广告案...

在第20个世界知识产权日到来之际&#xff0c;北京海淀法院通过“北京法院云法庭”公开开庭审理原告优酷信息技术(北京)有限公司(下称优酷公司)与被告北京搜狗科技发展有限公司、被告北京搜狗信息服务有限公司(下合称搜狗公司)涉搜狗浏览器插件屏蔽优酷视频广告不正当竞争纠纷案…

搜狗浏览器屏蔽广告插件_“云法庭”里“云勘验”,海淀法院开庭审理搜狗浏览器插件屏蔽优酷视频广告不正当竞争纠纷案...

来源&#xff1a; 北京海淀法院 特别提示&#xff1a;凡本号注明“来源”或“转自”的作品均转载自媒体&#xff0c;版权归原作者及原出处所有。所分享内容为作者个人观点&#xff0c;仅供读者学习参考&#xff0c;不代表本号观点。 在第20个世界知识产权日到来之际&#xff0…

搜狗浏览器屏蔽广告插件_“云法庭”里“云勘验”法院开审搜狗浏览器插件屏蔽优酷视频广告案...

在第20个世界知识产权日到来之际&#xff0c;北京海淀法院通过“北京法院云法庭”公开开庭审理原告优酷信息技术(北京)有限公司(下称优酷公司)与被告北京搜狗科技发展有限公司、被告北京搜狗信息服务有限公司(下合称搜狗公司)涉搜狗浏览器插件屏蔽优酷视频广告不正当竞争纠纷案…

【视频广告位叫法】

例如&#xff1a;爱奇艺&#xff0c;优酷&#xff0c;腾讯视频&#xff0c;前贴&#xff0c;中插&#xff0c;暂停贴&#xff0c;后贴广告位&#xff01;

优酷 DSP 广告投放系统架构实践

作者 | 鸿雁 阿里文娱技术专家 导读&#xff1a;随着 RTB 网络在线展现广告交易模式的兴起&#xff0c;各大公司都纷纷搭建自己的 DSP ( Demand-Side Platform ) 广告投放系统进行获客。优酷在近几年也搭建 DSP 系统&#xff0c;并且在持续迭代。在这一过程中&#xff0c;经历…