亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

C/C++ 凸多邊形求對(duì)角線交點(diǎn)的示例代碼

 更新時(shí)間：2020年11月06日 10:19:43   作者：SPSITA  
這篇文章主要介紹了C/C++ 凸多邊形求對(duì)角線交點(diǎn)的示例代碼,代碼簡(jiǎn)單易懂，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下

題目描述

對(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)文章

最新評(píng)論