文章

2

粉丝

513

获赞

6

访问

16.1k

头像
1847 折线分割平面
P1847
发布于2021年2月5日 15:41
阅读数 7.8k

1.本题的思路来自以下这篇博客(https://blog.csdn.net/summerxiachen/article/details/63252964),这里根据博文所给提示自己总结这道题的一些思路。

2.第一次做的时候,我想着是先自己动手模拟一下,尝试在n=2的时候再加一条折线,但是不清楚自己有没有漏画,手动模拟失败。

3.看了这篇博客后,立马明白了自己的问题所在:

(1)这道题相对来说是比较复杂的,所以首先应当从简单的情形开始分析,即在平面中逐条加入直线,这种情况下要注意每添加一条直线,为了使增加的平面数达到最多,应该使新添加的直线分别与其他直线都有且仅有一个交点。这样当添加第n条直线后,会增加n-1个交点,而增加n-1个交点又会增加n个平面然后推增加两条直线的情况:在平面中每次添加两条平行直线,假设现在已经有2n-2条直线,当添加第2n-1条直线时,这条直线会与其他2n-2条直线各有一个交点,这样就会增加2n-1个平面;而添加第2n条直线时,由于这条直线和第2n-1条直线平行,则其只与其他2n-1条直线相交形成2n-2个交点,同时增加2n-1个平面。所以第n次添加两条直线时,会增加的平面数为:4n-2(n=1,2,3...).所以总面数为:1+4-2+8-2+12-2+16-2+...4n-2=2n²+1.

最后,本题的添加折线就是相当于由刚才的每次添加两条平行的直线变为添加两条源点在同一点上的两条不平行的射线,这样一变,便会减少一个面。所以总面数变成:2n²-n+1.

C++实现如下:

#include <iostream>

using namespace std;

int main() {
    int num;
    cin >> num;
    int n[num];
    for (int i = 0; i < num; ++i) {
        cin >> n[i];
    }
    for (int i = 0; i < num; ++i) {
        cout<<n[i]*n[i]*2-n[i]+1<<endl;
    }
    return ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发