题解：P4903 心碎

· · 题解

思路

我们得先看明白题目描述的是什么，不然连题目都做不了，题目描述简化之后，我们可以想到题目给了我们一个内外各有 n 个顶点的圆环，我们需要建立 n 条对应的线，把这个圆环分成尽量多的区域。

每画一条线，如果它不与其他的线相交，它就会把一个区域分成两个。

如果这条线和已有的 x 条线在圆内相交，它会被交点分成 x + 1 段，每一段又会多一个区域。

因此，要让区域尽量的多，就要让线多两两相交，而避免三线共点，因为三线共点反而会让区域数减少。

推导一下，就可以得知最大区域的公式是：

\frac{n^2}{2} + 1

有一个要注意的点是 \frac{n^2}{2} 要向下取整，接下来按照这个公式敲代码即可。

:::success[AC代码]

#include<bits/stdc++.h>
using namespace std;
long long n;
int main(){
    scanf("%lld",&n);
    printf("%lld",n*n/2+1);
    return 0; 
}

:::