Luogu

LOJ

分析

将整个蛋糕看做平面图,由欧拉公式可得

$$ R=2+E-V $$

考虑到圆上本来有 $n$ 个点,每四个点确定的两条线段会增加一个交点。于是

$$ V=n+{n\choose 4} $$

考虑到圆上本来有 $n$ 条弧,每两个点间就有一条线段,每两条线段相交会增加两条线段。于是

$$ E=n+{n\choose 2}+2{n\choose 4} $$

代回去

$$ R=2+n+{n\choose 2}+2{n\choose 4}-n-{n\choose 4}=2+{n\choose 2}+{n\choose 4} $$

注意到这个平面数是算了外面的无界域的,所以最后还要减掉 $1$ ,即答案为

$$ 1+{n\choose 2}+{n\choose 4} $$

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

int main() { int n;
    while (scanf("%d",&n)==1) {
        int a=n*(n-1)/2;
        int b=n*(n-1)*(n-2)*(n-3)/24;
        printf("%d\n",1+a+b);
    }
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 55 PM