欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C/C++ 凸多邊形求對角線交點的示例代碼

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

題目描述

對于一個 n 個頂點的凸多邊形，它的任何三條對角線都不會交于一點。請求出圖形中對角線交點的個數(shù)。

例如，6 邊形：

在這里插入圖片描述

這里可以注意到并沒有出現(xiàn)多條對角線交叉在一個點的情況。

輸入格式
輸入只有一行一個整數(shù) n，代表邊數(shù)。

輸出格式
輸出一行一個整數(shù)代表答案。

在這里插入圖片描述

數(shù)據(jù)規(guī)模與約定

在這里插入圖片描述

這里給出一個特別的例子

輸入是：
98765
輸出是：
3964374251598225115

特別注意，在這種情況下，答案的值已經(jīng)非常逼近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;
}

先選擇一條對角線，將多邊形分為兩個部分，一邊是一個點的，另一邊是剩下的點，兩邊的點相連形成的對角線與所選擇的對角線相交形成交點。
以此類推，現(xiàn)分為一邊是1個點的，然后這一邊的點逐漸增加，直到另外一邊也只剩下一個點為止。需要特別注意的是，這樣的每一組對角線都有n條，這樣重復計算了比如點a到點b和點b到點a，其實是同一條。再根據(jù)題意，每個交點是由兩個對角線形成的，而我們在計算點的時候用每條對角線都計算了一次，所以又重復計算了一遍。也就是說，這樣我們得到的answer是最終正確answer的四倍。
特別注意，我將乘n的操作挪到了外面，把除以4的操作提前了，避免在運算的過程中出現(xiàn)數(shù)據(jù)上溢的情況。

到此這篇關于C/C++ 凸多邊形求對角線交點的文章就介紹到這了,更多相關C++ 凸多邊形求對角線交點內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

相關文章

最新評論