首页 > 代码库 > 欧拉公式

欧拉公式

LRJ算法入门经典第二版上面写错了,害得我想了半天。。。

V : 点数, E :边数  F :面数

欧拉公式 V - E + F = 2;

V =  n + n / 4 sum(i * (n - 2 - i));  [ 0 <= i <= n - 2];

E = n + n / 2 sum((i * (n - 2 - i ) + 1); [ 0 <= i <= n - 2];

代码实现:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<string>
#include<sstream>
#include<ctime>
using namespace std;
#define _PI acos(-1.0)
#define INF (1 << 10)
#define esp 1e-9
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pill;
/*===========================================
===========================================*/
LL _V(LL n){  /*求点*/
    LL ans = 0;
    for(LL i = 0 ; i <= n - 2 ; i++)
        ans = ans + i * (n - 2 - i);
    LL _ans = n + n * ans / 4;
    return _ans;
}
LL _E(LL n){ /*求面*/
    LL ans = 0;
    for(LL  i = 0 ; i <= n - 2; i++)
        ans = ans + (i * (n - 2 - i) + 1);
    LL _ans = n + n * ans / 2;
    return _ans;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        LL N;
        scanf("%I64d",&N);
        LL V = _V(N);
        LL E = _E(N);
        printf("%I64d\n",1 + E - V);
    }
    return 0;
}