洛谷P2181 对角线(组合数)

题目描述

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

例如,6边形:

输入输出格式

输入格式:

第一行一个n,代表边数。

输出格式:

第一行输出交点数量

输入输出样例

输入样例#1:

3

输出样例#1: 

0

输入样例#2: 

6

输出样例#2: 

15

说明

50%的测试数据 3≤N≤100;

100%的测试数据 3≤N≤100000.

一道代码难度与思维难度成绝对反比的题目

首先由于不会有三条对角线交于一点,所以过某一个交点有且只能有2条对角线

而这两条对角线实质上是确定了4个顶点(也可以看做是一个四边形的两条对角线交于一点,求四边形的数量)。

因此我们只需要确定4个顶点就得到了这个唯一确定的交点。

因此我们只需要求这样4个顶点的搭配有多少个了

也就是从n个顶点中取4个出来。

根据组合数的公式,(如果你不知道组合数的公式可以这么推:第一次取可以n个点都是可以取的,第二次取的时候第一个取的点就不能取了,所以只能取(n-1)种,以此类推)

由于改变四个点的顺序不会改变对角线,因此是求的组合而不是排列,也就要除以4!,也就是24

于是我们就得到了公式: n (n-1) (n-2) * (n-3) / 24

输出用unsigned long long

#include<cstdio>
#include<iostream>
using namespace std;
main() {
    unsigned long long N;
    cin>>N;
    cout<<N * (N - 1) / 2  * (N - 2) / 3 * (N - 3) / 4;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大闲人柴毛毛

动态规划法(三)——最长公共子序列

问题描述 给定两个序列,求出它们的最长公共子序列。 如:序列X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a},则X和Y的最长公共子...

37140
来自专栏前端小叙

javaScript实现归并排序

归并排序是一个O(nlogn)的算法,其基本思想就是一个分治的策略,先进行划分,然后再进行合并,下面举个例子。有这样一组数据: {5,4,1,22,12...

34080
来自专栏PHP在线

php面试题(二)

1 <?php echo count (false); $a = count ("567") + count(null) + count(false); ec...

44980
来自专栏前端儿

前缀式计算

输入有多组测试数据,每组测试数据占一行,任意两个操作符之间,任意两个操作数之间,操作数与操作符之间都有一个空格。输入的两个操作数可能是小数,数据保证输入的数都是...

16810
来自专栏深度学习之tensorflow实战篇

python中list、array、matrix之间的基本区别

python科学计算包的基础是numpy, 里面的array类型经常遇到. 一开始可能把这个array和python内建的列表(list)混淆, 这里简单总结一...

879120
来自专栏五毛程序员

Cocos2d-x基础篇C++

32230
来自专栏数据结构与算法

P1062 数列

题目描述 给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列,例如,当k=3时,这个序列是: 1,3,4,9,...

30870
来自专栏Jack-Cui

Day3、Python

题目 输入一行字符,分别统计出其中英文字母、空格、数字和其它字符的个数。 1、程序分析     根据题意可知,需要用到字符串的操作方法。本题中要用到的三...

18200
来自专栏机器学习和数学

[编程经验] Python 中列表list介绍

列表是Python中非常重要的一种数据结构,使用频率非常高,本文主要介绍对于学习python的新手来说,需要掌握的一些基础知识。 1. 创建列表 ? 列表用中括...

38250
来自专栏武培轩的专栏

Leetcode#1.Two Sum(两数之和)

题目描述 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。 示例: 给定 nums ...

34670

扫码关注云+社区

领取腾讯云代金券