精华内容
下载资源
问答
  • 圆分割平面问题 题目描述:确定平面一般位置上的n个互相交叠的圆所形成的区域数。互相交叠是指每两个圆相交在不同的两个点上。不相交或相切的圆是不允许的。一般位置是指不存在有一个公共点的三个圆。 输入格式 第1行...

    圆分割平面问题

    题目描述:确定平面一般位置上的n个互相交叠的圆所形成的区域数。互相交叠是指每两个圆相交在不同的两个点上。不相交或相切的圆是不允许的。一般位置是指不存在有一个公共点的三个圆。
    输入格式
    第1行:1个整数n(1<=n<=100)

    输出格式
    第1行:1个整数,表示圆所分割的最大的区域数

    样例输入
    4
    样例输出
    14

    这道题虽说是个递推

    不过感觉递推时间似乎太长了
    于是我就想了个时间短的方法
    那就是可以去寻找通项公式
    这里呢我找出来发现通项公式是n*n-n+2
    那既然都找通项公式那后面也就没啥好说的了

    下面直接上代码

    #include<iostream>
    using namespace std;
    int main(){
        int a,b;
        cin>>a;//输入
        b=a*a-a+2;//通项公式
        cout<<b;//输出
        return 0;
    }
    
    展开全文
  • 平面圆分割(欧拉公式)+例题

    千次阅读 2018-08-11 21:00:30
    +n(n为分割的线) 四个点,两条线最多可以相交一点,共有V= +n 对于相交的两条线,形成4条线,除了原有的两条线外,又增加了两条线,所以E=2 + +n 则F=2+E-V= + +2 去掉外边的部分,则F=2+E-V= + ...

    以下所涉及到的定理不太理解的盆友可以参考《算法笔记》这本书组合数那一章节的内容,故此处不做过多解释

    以牛客网小白月赛5为例:

    链接:https://www.nowcoder.com/acm/contest/135/F
    来源:牛客网
     

    题目描述

        签到题来了,送你们一个Python秒的题。

        Apojacsleam来到了OI大陆,经过了连年征战,成为了一方国王。 

        Apojacsleam把他的王国命名为“Apo国”,Apo国的领土是一个标准的圆形。 

        Apojacsleam现在想封赏他的大臣,他在国境上建立了n个城市,要求他的大臣对这n个城市两两之间修建道路(道路是笔直的),把整个王国分成尽量多的区域,使得每一个大臣都有封土并且不会太大(以免谋反)。 

        于是Apojacsleam找你求助,他告诉你他打算建多少个城市,而你的任务是告诉他最多可以分成多少个部分。 

        说的太慢可是要被处死的,所以你必须要在1s之内回答。 

    输入描述:

    输入数据有多组,每组一行,一个正整数n,意义如“题目描述”

    输出描述:

    对于每一组数据输出一行描述答案:
    
    输出一个正整数k,表示最多分成k份。

    示例1

    输入

    复制

    2
    3

    输出

    复制

    2
    4

    样例解释(样例1和样例2一起解释了):

    示例2

    输入

    复制

    4
    5
    6

    输出

    复制

    8
    16
    31

    说明

    • 欧拉公式:V-E+F=2; V:vertex顶点。E:edge边 。F:face 面
    • 两点连成一条直线,对于圆域,有边数{C_{n}}^{2}+n(n为圆上分割的线)
    • 四个点,两条线最多可以相交一点,共有V={C_{n}}^{4}+n
    • 对于相交的两条线,形成4条线,除了原有的两条线外,又增加了两条线,所以E=2{C_{n}}^{4}+{C_{n}}^{2}+n
    • 则F=2+E-V={C_{n}}^{4}+{C_{n}}^{2}+2

    去掉圆外边的部分,则F=2+E-V={C_{n}}^{4}+{C_{n}}^{2}+1

    对于该题来讲,数据范围很小,开long long 直接列公式即可

    ac代码:

    #include <bits/stdc++.h>
    #define ll unsigned long long int
    using namespace std;
    int main()
    {
        ll n;
        while(scanf("%lld",&n)!=EOF)
        {
            ll ans=0;
            ans=n*(n-1)*(n-2)*(n-3)/24+n*(n-1)/2+1;
            printf("%lld\n",ans);
        }
        return 0;
    }

     

    牛客网暑期多校第八场G题:

    链接:https://www.nowcoder.com/acm/contest/146/G
    来源:牛客网
     

    题目描述

    Niuniu likes mathematics. He also likes drawing pictures. One day, he was trying to draw a regular polygon with n vertices. He connected every pair of the vertices by a straight line as well. He counted the number of regions inside the polygon after he completed his picture. He was wondering how to calculate the number of regions without the picture. Can you calculate the number of regions modulo 1000000007? It is guaranteed that n is odd.

    输入描述:

    The only line contains one odd number n(3 ≤ n ≤ 1000000000), which is the number of vertices.

    输出描述:

    Print a single line with one number, which is the answer modulo 1000000007.

    示例1

    输入

    复制

    3

    输出

    复制

    1

    示例2

    输入

    复制

    5

    输出

    复制

    11

    备注:

    The following picture shows the picture which is drawn by Niuniu when n=5. Note that no three diagonals share a point when n is odd.

    可知F=2+E-V={C_{n}}^{4}+{C_{n}}^{2}+1-n,所有数都要开long long

    • 费马小定理:

    对于b/a%p,如果p为素数且a与p互质,那么a的(p-1)次方除以p的余数恒为1,
    a和a^(p-2)互为乘法逆元,则有 b/a%p=b*a^p-2%p

    再用迭代法快速幂求a^p-2

    对于组合数\large {C_{n}}^{m}  %p =  \large \frac{n! }{(n-m)!m!}   %p   =     \large \frac{\frac{n!}{(n-m)!}}{m!}   %p   =\large \frac{n!}{(n-m)!}   \large (m!)^{p-2}  %p

    所以最简单的做法为直接列式子,用费马小定理求逆元即可

    ac代码:

    #include<iostream>
    using namespace std;
    long long mod=1e9+7;
    long long pow(long long a,long long b)//求a^b
    {
        long long ans=1,ret=a;
        while(b)
        {
            if(b&1) ans=ans*ret%mod;
            ret=ret*ret%mod;
            b>>=1;
        }
        return ans;
    }
    int main()
    {
        long long n;
        scanf("%lld",&n);//c(n,4)+c(n,2)+1-n
        long long sum1=0,sum2=0,sum=0;
        sum1=n*(n-1)%mod*(n-2)%mod*(n-3)%mod*pow(24,mod-2)%mod;
        sum2=n*(n-1)%mod*pow(2,mod-2)%mod;//其实pow(2,mod-2)也可以写成(mod+1)/2,因为((mod+1)/2*2)%mod=1;但前提是mod是质数
        sum=(sum1+sum2+1-n+mod)%mod;//注意1-n是负数,所以要写成减法取模的形式,否则只过85%
        printf("%lld\n",sum);
        return 0;
    }

    或者把后面两项合并一下

    #include<iostream>
    using namespace std;
    long long mod=1e9+7;
    long long pow(long long a,long long b)//求a^b
    {
        long long ans=1,ret=a;
        while(b)
        {
            if(b&1) ans=ans*ret%mod;
            ret=ret*ret%mod;
            b>>=1;
        }
        return ans;
    }
    int main()
    {
        long long n;
        scanf("%lld",&n);//c(n,4)+c(n,2)+1-n
        long long sum=0;
        sum=n*(n-1)%mod*(n-2)%mod*(n-3)%mod*pow(24,mod-2)%mod;
        sum=(sum+(n-1)*(n-2)%mod*pow(2,mod-2)%mod)%mod;
        printf("%lld\n",sum);
        return 0;
    }
    • 当m和n的数据范围达到1e+18且mod为素数时,要用卢卡斯定理,同时内层嵌套费马小定理(此处也可以不用卢卡斯定理,因为\large {{C_{n}}^{m}}m和n的数据范围没有那么大,但先暂且保留着吧)

    ac代码:(此题也可以不用此方法做,用简单方法即可,但为了以后碰到其他相似求组合数取模的问题可以快速作答,此处依旧放上代码)

    #include <iostream>
    #include <cmath>
    #define ll unsigned long long int
    const ll mod=1000000007;
    using namespace std;
    ll pow(ll a,ll b )//用迭代法求快速幂a^b%mod,即逆元
    {
        ll ans=1,ret=a;
        while(b)
        {
            if(b&1) ans=ans*ret%mod;
            ret=ret*ret%mod;
            b>>=1;
        }
        return ans;
    }
    ll c(ll n,ll m)//用费马小定理求c(n,m)
    {
        ll fac=1;
        for(ll i=1;i<=m;i++)
        {
            fac=fac*(n-m+i)%mod;
            fac=fac*pow(i,mod-2)%mod;//每一次都要求快速幂,这样最后就是m!的mod-2次方了,也可先求之前列出的费马小定理的公式的左半部分的阶乘,再求右半部分阶乘的快速幂
        }
        //cout<<fac<<endl;
        return fac;
    }
    ll lucas(ll n,ll m)
    {
        if(m==0) return 1;
        return c(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;
    }
    int main()
    {
        ll n,sum1=0,sum2=0,sum=0;
        scanf("%lld",&n);
            sum1=lucas(n,4);
            sum2=lucas(n,2);
            //cout<<sum1<<" "<<sum2<<endl;
            sum=(sum1+sum2+1-n+mod)%mod;//减法取模
            printf("%lld\n",sum);
        return 0;
    }
    • 或者不用费马小定理求逆元,用扩展欧几里得算法求逆元(个人认为代码不是很好记,所以还是采用上面的方法吧)

    ac代码:

    #include<iostream>
    using namespace std;
    long long mod=1e9+7;
    long long extend_gcd(long long a, long long b, long long &x, long long &y) {
        if (b == 0) {
            x = 1, y = 0;
            return a;
        }
        else {
            long long r = extend_gcd(b, a % b, x, y);
            long long temp=x;
            x=y;
            y=temp-a/b*y;
            return r;
        }
    }
    long long inv(long long a, long long n) {
        long long x, y;
        extend_gcd(a, n, x, y);
        x = (x % n + n) % n;
        return x;
    }
    long long C(long long n,long long m)
    {
        long long ans=1;
        for(long long i=1;i<=m;i++)
        {
            ans=ans*(n-m+i)%mod;
            ans=ans*inv(i,mod)%mod;
        }
        return ans;
    }
    long long lucas(long long n,long long m)
    {
        if(m==0) return 1;
        return C(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;
    }
    int main()
    {
        long long n;
        scanf("%lld",&n);
        if(n>3)
            printf("%lld\n",(lucas(n,2)+lucas(n,4)-n+1+mod)%mod);
        else
            printf("1\n");
        return 0;
    }

    因为这道题对于\large {C_{n}}^{m}来说,m,n的数据范围没有达到1e+18,所以,可以省略卢卡斯定理

    ac代码:

    #include<iostream>
    using namespace std;
    long long mod=1e9+7;
    long long extend_gcd(long long a, long long b, long long &x, long long &y) {
        if (b == 0) {
            x = 1, y = 0;
            return a;
        }
        else {
            long long r = extend_gcd(b, a % b, x, y);
            long long temp=x;
            x=y;
            y=temp-a/b*y;
            return r;
        }
    }
    long long inv(long long a, long long n) {
        long long x, y;
        extend_gcd(a, n, x, y);
        x = (x % n + n) % n;
        return x;
    }
    long long C(long long n,long long m)
    {
        long long ans=1;
        for(long long i=1;i<=m;i++)
        {
            ans=ans*(n-m+i)%mod;
            ans=ans*inv(i,mod)%mod;
        }
        return ans;
    }
    int main()
    {
        long long n;
        scanf("%lld",&n);
        if(n>3)
            printf("%lld\n",(C(n,2)+C(n,4)-n+1+mod)%mod);
        else
            printf("1\n");
        return 0;
    }

    小白飘过~

    欢迎讨论,非诚勿扰哦~邮箱:1308989543@qq.com

    展开全文
  • HDU2050 折线分割平面   这种类型的题目,在acm编程中比较经典,这里我们由浅入深来学习下: (1)在一个平面上有一个和n条直线,这些直线中每一条在内同其他直线相交,假设没有3条直线相 交于一点,试问...

    HDU2050 折线分割平面

     

    这种类型的题目,在acm编程中比较经典,这里我们由浅入深来学习下:

    (1)在一个平面上有一个圆和n条直线,这些直线中每一条在圆内同其他直线相交,假设没有3条直线相

    交于一点,试问这些直线将圆分成多少区域。
    很容易看出递推关系,每新增一条直线,都将原来所有的区域分成两半,因此第n条直线会在原来的基础

    上再添加n个平面,函数递推关系式如下:

    递推公式1:

    f(0) = 1
    f(1) = 2
    f(2) = 4
    ...
    f(n) = f(n - 1) + n

    通项公式推导1:

    f(n)
    = f(n - 1) + n
    = f(n - 2) + n + (n - 1)
    = ...
    = f(0) + n + (n - 1) + ... + 1
    = 1 + (1 + n) * n / 2
    (2)若每次使用两条直线分割,即此时的n相当于原来的2n,可得:
    递推公式2:

    f(0) = 1
    f(1) = 4
    f(2) = 11
    ...
    f(n) = f(n - 1) + 2 * n - 1 + 2 * n = f(n - 1) + 4 * n - 1

    通项公式推导2_1:

    f(n)
    = f(n - 1) + (4 * n - 1)
    = f(n - 2) + 4 * (n - 1) - 1 + (4 * n - 1)
    = ...
    = f(0) + (4 * 1 - 1) + (4 * 2 - 1) + ... + (4 * n - 1)
    = 1 + 4 * (1 + 2 + .. + n) - n
    = 1 + 4 * (1 + n) * n / 2 - n
    = 1 + 2 * n * n + n

    上面的推导公式比较复杂,其实也可以直接将通项公式推导1中推导结果的n用2n替代,这样就容易理解多

    了:
    通项公式推导2_2:

    f(n)
    = 1 + (1 + (2 * n)) * (2 * n) / 2
    = 1 + 2 * n * n + n
    (3)若是普通直线,相交处所分割的平面为4份,而折线为两份,即每次分割比上面所考虑的情况少2份

    ,那么只要在上述情况的每次分割时减去2就能得到本题的结果了。

    递推公式3:

    f(n)
    = f(n - 1) + 4 * n - 1 - 2
    = f(n - 1) + 4 * n - 3
    通项公式:

    f(n)
    = 1 + 2 * n * n + n - 2 * n

    = 1 + 2 * n * n - n

     

    对于(3)这种类型,还有另外一种很好的解释(分享下!!):
    分割平面的个数=交点个数+顶点个数+1
    令f(n-1)为前n-1条折线分割的平面数,当添加第n条折线时。
    因为每一条边与前n-1条折线的两条边都相交,故增加的交点数为2*2*(n-1),顶点增加1,故
    f(n)=f(n-1)+4(n-1)+1
    f(n-1)=f(n-2)+4(n-2)+1
    ....
    f(2)=f(1)+4*1+1
    f(1)=2
    f(n)-2=4((n-1)+(n-2)+...+1)+(n-1)=4*((1+n-1)*(n-1)/2)+n-1=2(n*n-n)+n-1
    f(n)=2n^2-n+1

    可以得出公式f(n)=2n^2-n+1

    总结:

    直线:
    最多可分为(1/2)*n*(n+1)+1块区域
    折线:
    那就是可以分成(2×n^2-n+1)块区域

    展开全文
  • hdu,2050,折线分割平面

    2015-02-07 23:13:47
    (1)在一个平面上有一个和n条直线,这些直线中每一条在内同其他直线相交,假设没有3条直线相 交于一点,试问这些直线将分成多少区域。 很容易看出递推关系,每新增一条直线,都将原来所有的区域分成两半...
    这种类型的题目,在acm编程中比较经典,这里我们由浅入深来学习下:
    (1)在一个平面上有一个圆和n条直线,这些直线中每一条在圆内同其他直线相交,假设没有3条直线相

    交于一点,试问这些直线将圆分成多少区域。
    很容易看出递推关系,每新增一条直线,都将原来所有的区域分成两半,因此第n条直线会在原来的基础

    上再添加n个平面,函数递推关系式如下:

    递推公式1:

    f(0) = 1
    f(1) = 2
    f(2) = 4
    ...
    f(n) = f(n - 1) + n

    通项公式推导1:

    f(n)
    = f(n - 1) + n
    = f(n - 2) + n + (n - 1)
    = ...
    = f(0) + n + (n - 1) + ... + 1
    = 1 + (1 + n) * n / 2
    (2)若每次使用两条直线分割,即此时的n相当于原来的2n,可得:
    递推公式2:

    f(0) = 1
    f(1) = 4
    f(2) = 11
    ...
    f(n) = f(n - 1) + 2 * n - 1 + 2 * n = f(n - 1) + 4 * n - 1

    通项公式推导2_1:

    f(n)
    = f(n - 1) + (4 * n - 1)
    = f(n - 2) + 4 * (n - 1) - 1 + (4 * n - 1)
    = ...
    = f(0) + (4 * 1 - 1) + (4 * 2 - 1) + ... + (4 * n - 1)
    = 1 + 4 * (1 + 2 + .. + n) - n
    = 1 + 4 * (1 + n) * n / 2 - n
    = 1 + 2 * n * n + n

    上面的推导公式比较复杂,其实也可以直接将通项公式推导1中推导结果的n用2n替代,这样就容易理解多

    了:
    通项公式推导2_2:

    f(n)
    = 1 + (1 + (2 * n)) * (2 * n) / 2
    = 1 + 2 * n * n + n
    (3)若是普通直线,相交处所分割的平面为4份,而折线为两份,即每次分割比上面所考虑的情况少2份

    ,那么只要在上述情况的每次分割时减去2就能得到本题的结果了。

    递推公式3:

    f(n)
    = f(n - 1) + 4 * n - 1 - 2
    = f(n - 1) + 4 * n - 3
    通项公式:

    f(n)
    = 1 + 2 * n * n + n - 2 * n
    = 1 + 2 * n * n - n
    对于(3)这种类型,还有另外一种很好的解释(分享下!!):
    分割平面的个数=交点个数+顶点个数+1
    令f(n-1)为前n-1条折线分割的平面数,当添加第n条折线时。
    因为每一条边与前n-1条折线的两条边都相交,故增加的交点数为2*2*(n-1),顶点增加1,故
    f(n)=f(n-1)+4(n-1)+1
    f(n-1)=f(n-2)+4(n-2)+1
    ....
    f(2)=f(1)+4*1+1
    f(1)=2
    f(n)-2=4((n-1)+(n-2)+...+1)+(n-1)=4*((1+n-1)*(n-1)/2)+n-1=2(n*n-n)+n-1
    f(n)=2n^2-n+1

    可以得出公式f(n)=2n^2-n+1

    总结:

    直线:
    最多可分为(1/2)*n*(n+1)+1块区域
    折线:
    那就是可以分成(2×n^2-n+1)块区域

    展开全文
  • 平面图欧拉公式的精彩证明

    千次阅读 2017-09-20 20:57:27
    Euler公式是说,在一个由若干顶点和它们之间的一些不相交的边所组成的图中,等式V+F=E+2总成立,其中V表示顶点个数,E表示总的边数,F表示这个图分割出来的区域个数(包括一个“外部区域”,例如一个平面分割为...
  • 20个和20条直线最多能把平面分成多少个部分? [答案提交] 这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一 个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。 知识总结: ...
  • Taubin 在文章“由隐式方程定义的平面曲线、曲面和非平面空间曲线的估计,以及边缘和范围图像分割的应用”一文中提出,IEEE Trans。 帕米,卷。 13,第 1115-1138 页,(1991)。 注意:此方法将二次曲线(圆锥...
  • 题解:发现这相当于一个平面图,由欧拉公式得($F$为平面分割块数,$E$为平面图边数,$V$为平面图点数):$$F=E-V+2$$可知最优解不存在三线共点。 $V=n+\binom n4$,即上原来的$n$个点,和任意四个点会产生一个...
  • 题解:发现这相当于一个平面图,由欧拉公式得($F$为平面分割块数,$E$为平面图边数,$V$为平面图点数):$$F=E-V+2$$可知最优解不存在三线共点。 $V=n+\binom n4$,即上原来的$n$个点,和任意四个点会产生一个...
  • HDU-2050

    2014-07-09 00:22:53
    这题推起来还是能接受的,折线分割平面,应该从直线去推导折线的情况,而且直线分割平面是有现成公式可以用的 1条直线将平面分成 2 部分 2条直线将平面分成 4 = 2 + 2 部分 3条直线将平面分成 7 = 2 + 2 + 3 部分...
  • 题意:给定一个数量,求用,椭圆,三角形分割平面,分割出该数量,输出所有情况 思路:有公式2 + 2m(m-1) + n(n-1) + 4mn + 3p(p-1) + 6mp + 6np 由于m和p都是[0,100],所以可以枚举m和p,去求出n,然后判断...
  • 传送门 调了一下午才调出来。主要是这道题的数据太能构造了,导致每次改完都只能多过几个点。 对于这种问平面被图形分割成...由于这道题几个分割可以不连通,改一下公式即可: V−E+R=C+1 V-E+R=C+1 V−E+R=C+1...
  • 计蒜客题目  一道组队赛题目,当时猜着是有什么规律,但是我们都不太擅长找规律,gg的一道题,今天补题时第一次了解到欧拉定理,这道题目就是用欧拉定理做的...这道题目让我们求最多能分割几个平面,因此这里 +...
  • uva 10519 - !! Really Strange !!(规律)

    千次阅读 2013-11-02 17:26:56
    题目大意:给出n,问用n个最多能将平面分割成几份。 解题思路:公式c[i] = i * i - i + 2,首先可以分析出c[i] = c[i - 1] + 2 * i - 2, 然后带入c[i - 1] = c[i - 2] + 2 * (i - 1) - 2,重复带入可得c[i] = ...
  • 1.16.6 存不存在一个平面把两堆点分开(poj3643) 66 1.16.7 pku_3335_判断多边形的核是否存在 67 1.16.8 pku_2600_二分+的参数方程 74 1.16.9 pku_1151_矩形相交的面积 76 1.16.10 pku_1118_共线最多的点的个数 78 ...
  •  黄家礼编著的《几何明珠(第3版)》以著名的平面几何定理为素材,系统地介绍了这些定理的历史渊源及各种巧妙简捷的证明与解法,得出许多美妙有趣的引申和推广,并挖掘出这些定理在解题中的一些典型新颖的应用。...
  • 技巧61 在图表中显示趋势线的公式 技巧62 利用趋势线进行预测 技巧63 选择正确的趋势线类型 技巧64 移动平均趋势线 技巧65 移动平均折线图 技巧66 为数据系列添加误差线 技巧67 美化误差线 技巧68 自定义误差量的妙...
  • Python 科学计算

    2018-09-20 16:59:31
    4.4.1 平面几何...................................133 4.4.2 绘图...........................................135 第 5 章 matplotlib——绘制精美 的图表..................................... 139 5.1 快速...
  • 如何通俗易懂地解释欧拉公式(e^πi+1=0)? 欧拉公式将指数函数的定义域扩大到了复数域,建立和三角函数和指数函数的关系,被誉为“数学中的天桥” 1、从自然数扩张到整数:...1、在复平面上画一个单位,单位

空空如也

空空如也

1 2
收藏数 24
精华内容 9
关键字:

圆分割平面公式