C/C++ 凸多邊形求對(duì)角線交點(diǎn)的示例代碼
題目描述
對(duì)于一個(gè) n 個(gè)頂點(diǎn)的凸多邊形，它的任何三條對(duì)角線都不會(huì)交于一點(diǎn)。請(qǐng)求出圖形中對(duì)角線交點(diǎn)的個(gè)數(shù)。
例如，6 邊形：
這里可以注意到并沒有出現(xiàn)多條對(duì)角線交叉在一個(gè)點(diǎn)的情況。
輸入格式
輸入只有一行一個(gè)整數(shù) n，代表邊數(shù)。
輸出格式
輸出一行一個(gè)整數(shù)代表答案。
數(shù)據(jù)規(guī)模與約定
這里給出一個(gè)特別的例子
輸入是：
98765
輸出是：
3964374251598225115
特別注意，在這種情況下，答案的值已經(jīng)非常逼近longlong類型的最大表示范圍，所以在計(jì)算的過程當(dāng)中要特別注意，下面給出代碼
#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;
}
先選擇一條對(duì)角線，將多邊形分為兩個(gè)部分，一邊是一個(gè)點(diǎn)的，另一邊是剩下的點(diǎn)，兩邊的點(diǎn)相連形成的對(duì)角線與所選擇的對(duì)角線相交形成交點(diǎn)。
以此類推，現(xiàn)分為一邊是1個(gè)點(diǎn)的，然后這一邊的點(diǎn)逐漸增加，直到另外一邊也只剩下一個(gè)點(diǎn)為止。需要特別注意的是，這樣的每一組對(duì)角線都有n條，這樣重復(fù)計(jì)算了比如點(diǎn)a到點(diǎn)b和點(diǎn)b到點(diǎn)a，其實(shí)是同一條。再根據(jù)題意，每個(gè)交點(diǎn)是由兩個(gè)對(duì)角線形成的，而我們?cè)谟?jì)算點(diǎn)的時(shí)候用每條對(duì)角線都計(jì)算了一次，所以又重復(fù)計(jì)算了一遍。也就是說，這樣我們得到的answer是最終正確answer的四倍。
特別注意，我將乘n的操作挪到了外面，把除以4的操作提前了，避免在運(yùn)算的過程中出現(xiàn)數(shù)據(jù)上溢的情況。
到此這篇關(guān)于C/C++ 凸多邊形求對(duì)角線交點(diǎn)的文章就介紹到這了,更多相關(guān)C++ 凸多邊形求對(duì)角線交點(diǎn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要給大家介紹了關(guān)于C++命令行解析包gflags的使用教程，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
這篇文章主要介紹了詳解在VScode中添加代碼塊(含C++指令生成代碼)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-04-04
Qt學(xué)習(xí)教程之對(duì)話框消失動(dòng)畫效果
這篇文章主要給大家介紹了關(guān)于Qt學(xué)習(xí)教程之對(duì)話框消失動(dòng)畫效果的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2018-07-07
C++控制臺(tái)實(shí)現(xiàn)密碼管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++控制臺(tái)實(shí)現(xiàn)密碼管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-11-11
通過c++11改進(jìn)我們的模式之改進(jìn)命令模式
這篇我要講的是如何使用c++11改進(jìn)命令模式，感興趣的朋友可以看下2013-11-11
C/C++實(shí)現(xiàn)string和int相互轉(zhuǎn)換的常用方法總結(jié)
在C++編程中,經(jīng)常需要在字符串（string）和整型（int）之間進(jìn)行轉(zhuǎn)換,本文將詳細(xì)介紹幾種在C和C++中實(shí)現(xiàn)這兩種類型轉(zhuǎn)換的常用方法,有需要的可以參考下2024-01-01
二叉樹中葉子節(jié)點(diǎn)的統(tǒng)計(jì)和樹高問題
今天小編就為大家分享一篇關(guān)于二叉樹中葉子節(jié)點(diǎn)的統(tǒng)計(jì)和樹高問題，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2019-03-03
這篇文章主要介紹了C++中類的構(gòu)造函數(shù)初始值列表，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-11-11
作用域規(guī)定了標(biāo)識(shí)符在代碼中的可見性和可訪問性,全局作用域中的標(biāo)識(shí)符可以在整個(gè)程序中使用,局部作用域中的標(biāo)識(shí)符只能在其所在的代碼塊中使用,而命名空間作用域提供了一種組織和封裝代碼的方式,以避免命名沖突,這篇文章主要介紹了C++中的作用域,需要的朋友可以參考下2024-02-02
大家好，本篇文章主要講的是帶你了解C++中vector的用法，感興趣的同學(xué)趕快來看一看吧，對(duì)你有幫助的話記得收藏一下2022-01-01