C/C++ 凸多边形求对角线交点的代码实例
SPSITA 人气:0题目描述
对于一个 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的操作提前了,避免在运算的过程中出现数据上溢的情况。
加载全部内容