精华内容
下载资源
问答
  • 计算直线交点数 Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other) Total Submission(s) : 44 Accepted Submission(s) : 21 Font: Times New Roman | Verdana | Georgia...

    计算直线的交点数

    Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)
    Total Submission(s) : 44   Accepted Submission(s) : 21

    Font: Times New Roman | Verdana | Georgia

    Font Size:  

    Problem Description

    Input

    输入数据包含多个测试实例,每个测试实例占一行,每行包含一个正整数n(n<=20),n表示直线的数量.

    Output

    每个测试实例对应一行输出,从小到大列出所有相交方案,其中每个数为可能的交点数,每行的整数之间用一个空格隔开。

    Sample Input

    2
    3
    

    Sample Output

    0 1
    0 2 3
    

    Author

    lcy

    Source

    ACM暑期集训队练习赛(九)

    # include<stdio.h>
    int main()
    {
        int i,j,k,m,n;
        int a[22][200];
        for(i=0; i<190; i++)
            a[0][i]=0;
        for(i=1; i<=20; i++)
        {
            a[i][0]=1;
            for(j=1; j<=(i-1)*i/2; j++)
                a[i][j]=0;
            for(j=1; j<i; j++)
            {
                m=i-j;
                for(k=0; k<=m*(m-1)/2; k++)
                {
                    if(a[m][k]==1)
                        a[i][k+j*m]=1;
                }
            }
        }
        while(scanf("%d",&n)!=EOF)
        {
            printf("0");
            for(i=1; i<=n*(n-1)/2; i++)
            {
                if(a[n][i]==1)
                    printf(" %d",i);
            }
            printf("\n");
        }
        return 0;
    }
    

    分析:

    将n条直线排成一个序列,两条直线最多只有一个交点,三条直线最多有两个交点,直线n 和其他n-1条直线最多有n-1个交点。

    由此得出n条直线互不平行且无三线共点的最多交点数:

      Max = 1 +2 +……+(n-1)=n(n-1)/2

    但本题不这么简单,

    这些直线有多少种不同的交点数?

     

    容易列举出i=1,2,3的情况如右图所示,

    来分析n=4的情况:

    1. 四条直线全部平行,无交点

    2. 其中三条平行,交点数: (n-1)*1+0=3;

    3. 其中两条平行,而另外两条直线的交点既可能平行也可能相交,因此交点数据分别为:

      (n-2)*2+0=4

        (n-2)*2+1=5

    4. 四条直线互不平行, 交点数为(n-3)*3+3条直线的相交情况:

      (n-3)*3+0=3 
      (n-3)*3+2=5 
      (n-3)*3+3=6

    即n=4时,有0,3, 4, 5, 6个不同的交点数。

    从上述n=4的分析过程中,发现:

    m条直线的交点数=(m-r)条平行线与r条直线交叉的交点数+r条直线本身的交点数=

    (m-r)*r+r条直线之间的交点数。



    #include<stdio.h>
    #include<string.h>
    const int MAX=200;
    int main()
    {
        int n,i,j,k;
        int line[21][MAX];
        memset(line[1], 0, sizeof(line[1]));
        line[1][0]=1;
    for (i=2; i<=20; i++)    //计算当直线个数为i时的交点情况
        {
            memset(line[i], 0, sizeof(line[i]));
            line[i][0]=1;    //无论有几条直线,都会存在交点个数为0的这种情况
            for (j=1; j<i; j++)    //对i条直线进行划分
            {
                for (k=0; k<MAX; k++)    //计算该种划分情况下,交点的个数
                {
                    if (line[j][k]==1)
                    {
                        line[i] (i-j)*j+k]=1;    //line[i] (i-j)*j+k]=1表示存在交点个数为(i-j)*j+k
                    }
                }
            }
        }
    while (scanf("%d", &n)!=EOF)
        {
            for (i=0; i<MAX; i++)
            {
                if (i==0) printf("0");
                else if(line[n][i]==1) printf(" %d", i);
            }
            printf("\n");
        }
        return 0;
    }
    


    展开全文
  • n条直线最多个交点

    2020-03-13 18:56:56
    // n条直线最多交点 /******************* 减而治之,把第n条直线单独拿出来 1.定义问题,考虑几参数 f(n)表示n条直线 最多交点数 2.找相似性(试探) f(n) = f(n-1) + (n-1) 3.确定递归出口(特殊情况) f(1) ...

    递归算法的简单运用 

    // n条直线最多几个交点
    /*******************
    减而治之,把第n条直线单独拿出来
    1.定义问题,考虑几个参数
    	f(n)表示n条直线 最多交点数
    2.找相似性(试探)
    	f(n) = f(n-1) + (n-1)
    3.确定递归出口(特殊情况)
    	f(1) = 0 
    ******************/
    #include<bits/stdc++.h>
    using namespace std;
    int f(int n);
    int main(){
    	int n;
    	while(cin>>n){
    		cout<<f(n)<<endl;
    	}
    	return 0;
    }
    int f(int n){
    	if(n==1)
    		return 0;
    	else return f(n - 1) + (n - 1);
    }

     

    展开全文
  • 它与前面的3条直线最多有3个交点,这3交点将第4条直线分成4段,其中每段将原来所在平面部分一分为二,所以4条直线最多将平面分成7+4=11部分. 完全类似地,5条直线最多将平面分成11+5=16部分;6条直线...

    1条直线最多将平面分成2个部分;2条直线最多将平面分成4个部分;3条直线最多将平面分成7个部分;现在添上第4条直线.它与前面的3条直线最多有3个交点,这3个交点将第4条直线分成4段,其中每一段将原来所在平面部分一分为二,所以4条直线最多将平面分成7+4=11个部分.

    完全类似地,5条直线最多将平面分成11+5=16个部分;6条直线最多将平面分成16+6=22个部分;7条直线最多将平面分成22+7=29个部分;8条直线最多将平面分成29+8=37个部分.

    一般地,n条直线最多将平面分成2+2+3....+N=1/2(N的平方+N+2)。
    20条直线可以把平面分成0.5*(20*20+20+2)=221部分

    展开全文
  • 首先考虑 n条直线最多把平面分成an部分 于是a0=1 a1=2 a2=4 对于已经n条直线 将平面分成了最多的an块 那么加一条直线 他最多与前n条直线n个交点 于是被它穿过的区域都被一分为二 那么增加的区域数就是穿过的...

    看了一道水题,发现这个两个问题值得记录一下。



    一,直线分割平面:



    首先考虑 n条直线最多把平面分成an部分

    于是a0=1 a1=2 a2=4

    对于已经有n条直线 将平面分成了最多的an块

    那么加一条直线 他最多与前n条直线有n个交点 于是被它穿过的区域都被一分为二 那么增加的区域数就是穿过的区域

    数 也就是这条直线自身被分成的段数 就是n+1 故 a(n+1) = an+n+1

    an = n+(n-1)+...+2+a1 = n(n+1)/2 +1



    二,平面分割空间:



    设n个平面最多把空间分成bn个部分

    于是b0=1 b1=2 b2=4

    对于已经有n个平面 将空间分成了最多的bn块

    那么加入一个平面 它最多与每个平面相交 在它的上面就会得到至多n条交线

    同时被它穿过的空间区域也被它一分为二 那么增加的区域数仍旧是它穿过的区域数 也就是这个平面自身被直线分割

    成的块数 就是an

    于是b(n+1)=bn+an

    bn=a(n-1)+b(n-1)=...=a(n-1)+a(n-2)+...+a1+b1

    =(n-1)n/2 +(n-2)(n-1)/2+...+1*(1+1)/2+n+2

    =求和[1方到(n-1)方]/2 + 求和[1到(n-1)]/2 +n+1

    =n(n-1)(2n-1)/12 +n(n-1)/4 +n+1

    =n(n+1)(n-1)/6 +n+1

    =(n^3+5n+6)/6



    三,直线分割空间:


    由上所述,直接可以得到公式: an = (n*(n+1)/2+1) * (n^3+5n+6)/6

                                                            = (n^5+n^4+7*n^3+11*n^2+16*n)/12+1


    四,折线分割平面:


     根据直线分平面可知,由交点决定了射线和线段的条数,进而决定了新增的区域数。当n-1条折线时,区域数为f(n-1)。为了使增加的区域最多,则折线的两边的线段要和n-1条折线的边,即2*(n-1)条线段相交。那么新增的线段数为4*(n-1),射线数为2。但要注意的是,折线本身相邻的两线段只能增加一个区域。


     故:f(n)=f(n-1)+4(n-1)+2-1

                          =f(n-1)+4(n-1)+1

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

                         ……

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

                         =2n^2-n+1




    
    展开全文
  • 需求:给定一个二维平面,平面上 n 个点,求最多有多少个点在同一条直线上。 分析思路: 1、将所有点二维坐标化,即定义出所有点的x,y坐标值 2、遍历出所有取出点的情况(不考虑先后顺序),根据任意点都确定一...
  • 计算直线的交点数 ...将n条直线排成一个序列,直线2和直线1最多只有一个交点,直线3和直线1,2最多有两个交点,……,直线n 和其他n-1条直线最多有n-1个交点。由此得出n条直线互不平行且无三线共点的最多交点
  • 给出2D平面中的n坐标点,计算最多有多少点在一条直线一条直线可以用斜率表示,即如果已知(x1,y1),(x2,y2)" role="presentation" style="position: relative;">(x1,y1),(x2,y2)(x1,y1),(x2,y2)
  • 、题目描述   二、思路: ... (3)直线n,与其他的n-1条直线最多有n-1个交点  归纳:n条直线互不平行且无三线共点的交点数最多为:Max = 1 +2 +……+(n-1)=n(n-1)/2;    n条直线多少种...
  • 计算直线交点

    2014-04-01 19:06:12
    计算直线的交点数 ...将n条直线排成一个序列,直线2和直线1最多只有一个交点,直线3和直线1,2最多有两个交点,……,直线n 和其他n-1条直线最多有n-1个交点。由此得出n条直线互不平行且无三线共点的最多交点
  • 两条直线交点坐标

    千次阅读 2017-10-11 21:18:00
    遂从最简单的直角坐标系两条直线交点开始, 直线1的方程解析式: 2x-y=0; 直线2的方程解析式: 4x-5y=9; 记录下思考过程 版本 //求直角坐标系中直线2x-y=0 和 4x-5y=9的交点坐标 $x = 0; $...
  • n条直线最多一个平面拆成1+(n+1)*n/2个区域, 请问:n个平面最多把一个空间拆成多少个区域?(n>=0) 这个问题我想了挺久,后来在网上搜,并且也搜到了很详细的解答,但是没有看,我还是希望能自己想出来...
  • 题目: n平面把空间最多分成几...分析:要n条直线最多把平面分成若干部分,必须n条直线两两相交且无3条过同一点,记n条直线最多可以把平面分成an部分,第n条直线与前n-1 条直线最多有n-1个交点,这些交点把第n条直...
  • 首先自我检讨一下,最近忙一些杂事导致OJ与红宝进度严重滞后,今后要学会专注,回避一些不必要的事情。...直线n和其他n-1条直线最多有n-1个交点,由此得出n条直线互不平行且无三线共点的最多交点数: ...
  • 将n 条直线排成一个序列,直线2和直线1最多只有一个交点,直线3和直线1,2最多有两个交点,。。。。。。,直线n 和其他n-1条直线最多有n-1个交点。由此得出n条直线互不平行且无三线共点的最多交点数:Max = 1 +2 +。...
  • 计算直线交点数—动态规划

    千次阅读 2011-07-26 00:02:43
    计算直线的交点数Problem Description平面上n条直线,且无三线共点,问这些直线能多少种不同交点数。...问题分析将n条直线排成一个序列,直线2和直线1最多只有一个交点,直线3和直线1,2最多有两交点,
  • 写的小例子,备份 ...value1){ var length:int = clickPoint.length; startPoint.text = clickPoint[length-2].x + "," +clickPoint[length-2].y; endPoint.text = p.x + ",...
  • 他发现:把整个天空看做一个平面直角坐标系,飞行路径是所有过任意个端点的直线。 如果这些飞机可能会撞在一起,或者说只要这些直线有交点,就可能发生事故。 在所有直线中应该最少删除多少条直线使得剩下的直线...
  •   最近在水面无人艇(USV)模拟仿真中,用到了一些点和线的关系求解,本文主要讲述一下两点确认直线,点到直线距离,两条直线交点等问题的解决方法,并给出python程序。部分内容非原创,文中给出链接,需要者...
  • 题目描述 平面内n条直线两两相交,...已有两条直线时增加条直线,增加两个交点,已三条直线时增加条直线,增加三个交点次类推,交点的个数为等差数列#include <stdio.h>int main() { int n,sum=0,i; sca
  • 由N-1趟(pass)排序组成,经过第一次排序后把最小的放到了0位置(比较了N-1次),接着第二趟把第二小的放在1位置……N-1趟之后就是一个有序数组了。 冒泡排序: 在要排序的一组数中,对当前还未排好序的范围内的...
  • 二维平面内两直线交点计算

    千次阅读 2019-03-08 22:03:17
    二维平面内两直线交点计算
  • n条直线互不平行且无三线共点的最多交点数max=1+2+……(n-1)=n(n-1)/2, 所以n=20的话,最大的交点数是190 本题是求多少种交点数: 容易列举出N=1,2,3的情况: 0 0,1 0,2,3 如果已知 1、第四条与...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,695
精华内容 1,478
关键字:

两条直线最多有1个交点