C/C++ 凸多边形求对角线交点的示例代码

题目描述

对于一个 n 个顶点的凸多边形，它的任何三条对角线都不会交于一点。请求出图形中对角线交点的个数。

例如，6 边形：

这里可以注意到并没有出现多条对角线交叉在一个点的情况。

输入格式
输入只有一行一个整数 n，代表边数。

输出格式
输出一行一个整数代表答案。

数据规模与约定

这里给出一个特别的例子

输入是：
98765
输出是：
3964374251598225115

特别注意，在这种情况下，答案的值已经非常逼近longlong类型的最大表示范围，所以在计算的过程当中要特别注意，下面给出代码

#include <iostream>

using namespace std;

int main()
{
	long long int n = 0;
	cin >> n;
	long long int answer = 0;
	long long int temp = 1;
	while (temp < (n - 2))
	{
		answer += temp * (n - temp - 2);
		temp++;
	}
	if (n % 4 == 0)
	{
		n /= 4;
	}
	else if (n % 2 == 0)
	{
		n /= 2;
		answer /= 2;
	}
	else
	{
		answer /= 4;
	}
	answer *= n;
	cout << answer << endl;
	return 0;
}

先选择一条对角线，将多边形分为两个部分，一边是一个点的，另一边是剩下的点，两边的点相连形成的对角线与所选择的对角线相交形成交点。
以此类推，现分为一边是1个点的，然后这一边的点逐渐增加，直到另外一边也只剩下一个点为止。需要特别注意的是，这样的每一组对角线都有n条，这样重复计算了比如点a到点b和点b到点a，其实是同一条。再根据题意，每个交点是由两个对角线形成的，而我们在计算点的时候用每条对角线都计算了一次，所以又重复计算了一遍。也就是说，这样我们得到的answer是最终正确answer的四倍。
特别注意，我将乘n的操作挪到了外面，把除以4的操作提前了，避免在运算的过程中出现数据上溢的情况。

到此这篇关于C/C++ 凸多边形求对角线交点的文章就介绍到这了,更多相关C++ 凸多边形求对角线交点内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C/C++ 凸多边形求对角线交点的示例代码

    题目描述 对于一个 n 个顶点的凸多边形,它的任何三条对角线都不会交于一点.请求出图形中对角线交点的个数. 例如,6 边形: 这里可以注意到并没有出现多条对角线交叉在一个点的情况. 输入格式 输入只有一行一个整数 n,代表边数. 输出格式 输出一行一个整数代表答案. 数据规模与约定 这里给出一个特别的例子 输入是: 98765 输出是: 3964374251598225115 特别注意,在这种情况下,答案的值已经非常逼近longlong类型的最大表示范围,所以在计算的过程当中要特别注意,下面给出

  • Python求字符串的长度示例代码

    目录 Python求字符串的长度 补充:Python计算字符串长度的函数 Python三种计算字符串长度的函数 1.使用内置函数len 2.使用for循环 3.使用while循环和切片 Python求字符串的长度 python 写一个函数,求一个字符串的长度,在main函数中输入字符串,并输出其长度. def func(a): #定义一个求字符串长度的函数 '求一个字符串的长度' len=0 for i in a: len+=1 return len if __name__=='__main__

  • Python求离散序列导数的示例

    有一组4096长度的数据,需要找到一阶导数从正到负的点,和三阶导数从负到正的点,截取了一小段. 394.0 388.0 389.0 388.0 388.0 392.0 393.0 395.0 395.0 394.0 394.0 390.0 392.0 按照之前所了解的,对离散值求导其实就是求差分,例如第i点的导数(差分)为: 即在一个宽度为2m+1的窗口内通过计算前后m个值加权后的和得到.但是在实际使用过程中效果不是很好.于是想到了同样在一个宽度为2k+1的窗口内,将这2k+1个点拟合成一个函数

  • python 求定积分和不定积分示例

    求f(x) = sin(x)/x 的不定积分和负无穷到正无穷的定积分 sin(x)/x 的不定积分是信号函数sig ,负无穷到正无穷的定积分为pi import math import numpy as np import matplotlib.pyplot as plt from sympy import * #用于求导积分等科学计算 def draw_plot_set():#设置画图格式 ax = plt.gca() #改变坐标轴位置 ax.spines['right'].set_color

  • Pandas DataFrame求差集的示例代码

    Pandas DataFrame求差集的示例代码

    在Pandas中 求差集没有专门的函数.处理办法就是将两个DataFrame追加合并,然后去重. divident.append(hasThisYearDivident) noHasThisYearDivident = divident.drop_duplicates(subset='ts_code', keep=False, inplace=True, ignore_index=True) 具体函数用法: https://pandas.pydata.org/pandas-docs/stable

  • 利用Hadoop实现求共同好友的示例详解

    利用Hadoop实现求共同好友的示例详解

    目录 前言 业务分析 实现思路分析 编码实现 1.第一个map类 2.第一个Reduce类 3.第一个Job类 4.第二个map类 5.第二个Reducer类 6.第二个Job类 前言 在很多社交APP中,比如大家熟悉的QQ好友列表中,打开会话框,经常可以看到下面有一栏共同好友的推荐列表,用户通过这种方式,可以添加潜在的关联好友 这种功能该如何实现呢?对redis比较了解的同学应该能很快想到,可以使用redis来实现这个功能.没错,redis确实是个不错的可以实现这个功能的方案. 但redis的

  • python开发任意表达式求值全功能示例

    目录 正文 完整的源代码 正文 在之前的基础上进一步实现了全功能表达式求值. 已支持浮点数 已支持字符串的处理,前加一个"(类似lisp语法) 支持减号/负号,一符两用机制 支持所有算术运算符,包括**,//, % 支持全部7个比较运算符 支持与或非3个逻辑运算符 支持自定义数学函数(代码中预设sin函数作为示范) 支持外部提供的变量机制 支持外部设置函数(代码中预设isvar函数作为示范) 支持列表 字典的支持,体现在外部的变量中 结构清晰,易于扩展 具有实用性及学习性 与其说距离DSL只有一

  • python实现经纬度采样的示例代码

    python实现经纬度采样的示例代码

    原理 经度 phi,纬度 theta 处的坐标为: x =R* cos(phi) * cos(theta) y = Rsin(phi) * cos(theta) z = Rsin(theta) 问题 经纬度采样的采样点是相同经纬度间隔的交点.但是采样1000个点,如何划分多少条经线,多少条纬线相交,才能使1000个采样点最均匀的分布在球面上(虽然经纬度采样本来就不均匀,但对于不同的采样点个数应该有一种相对最均匀的经纬线划分)?求大佬指教! 我目前是将纬度每10度进行划分. Code import

  • 利用Java快速查找21位花朵数示例代码

    前言 本文主要给大家介绍了关于利用Java快速查找21位花朵数的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. 以前备赛的时候遇到的算法题,求所有21位花朵数,分享一下,供大家参考,效率已经很高了. 示例代码 package com.jianggujin; import java.math.BigInteger; import java.util.ArrayList; import java.util.List; /** * 水仙花数 * * @author jian

  • Android实现用文字生成图片的示例代码

    Android实现用文字生成图片的示例代码

    本文介绍了Android实现用文字生成图片的示例代码,分享给大家,具体如下: 效果图 我们先来看看效果图,可以看到下图由各种颜色的"美"字拼接而成,形成了一张不一样的图片. 原理 生成这种图片的原理很简单,但是当时看开源项目时愣是看不懂,因为没学过Python,但是仔细研究,终于能慢慢的理解该开源项目源码,并把它改写成Android平台的源代码.下面把这个算法的主要内容讲给大家,该算法大致原理如下: 1.根据原图片的大小和字体的大小创建一张空白图片 2.把原图片按字体的大小分成若干块,

随机推荐