码蹄集直线

男娘i 2023-10-03 19:27 56阅读 0赞

### 一、题目 ###

如果用数学的观点来简化这个世界，将人生看做一条直线，那么世界上的一些人注定和我们平行或者异面。由这种人生哲理，我们可以考虑一下瓜大的同学—共可能有多少种交点数量。现在我们只考虑平面上的情况。**平面上有n条直线，且无三线共点，那么这些直线能有多少不同的交点数?**

### 二、格式 ###

输入： 一个整数n，表示n条直线(n <= 25)  
输出： 一个整数表示方案总数

### 三、样例 ###

输入： 4  
输出： 5

### 四、思路 ###

利用平面向量的知识解决，将线段视为向量  
但是开始要判断两条直线是否可能相交，即以两条直线为对角线的矩形没有公共区域。

### 五、代码 ###

#include <bits/stdc++.h>
    using namespace std;
    
    const int N = 1e4 + 1;
    int n;
    int p[26][N];
    
    int main()
    {
        
        cin >> n;
        memset(p, 0, sizeof p);
        for(int i = 0; i <= n; i ++){
        
            p[i][0] = 1;
        }
        for(int m = 2; m <= n; m ++){
        
            for(int i = 1; i < m; i ++){
        
                for(int j = 0; j <= 500; j ++){
        
                    if(p[m - i][j] == 1)
                        p[m][j + i*(m - i)] = 1;
                }
            }
        }
        int cnt = 0;
        for(int i = 0; i <= n*(n - 1) / 2; i ++){
        
            if(p[n][i]) cnt ++;
        }
        cout << cnt << endl;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，56人围观）

还没有评论，来说两句吧...

相关阅读

相关【码蹄集】四柱河内塔

题目：四柱河内塔河内塔问题：有三个柱子，编号为1，2，3;在编号为1的柱子上有n个大小不同圆盘，圆盘从小到大，从上到下堆叠，你只可以移动—个柱子上最上面的圆盘。

川长思鸟来/ 2023年10月03日 19:28/ 0 赞/ 47 阅读

相关【码蹄集】矩阵的对角线

题目：矩阵的对角线 ![在这里插入图片描述][568e0f29b6ec4561ae8df219ae4930a2.png] 格式 ![在这里插入图片描述][1e29

缺乏、安全感/ 2023年10月03日 19:28/ 0 赞/ 28 阅读

相关码蹄集迷宫2

一、题目：迷宫2 迷宫中有N堵圆形的墙。两个人被困在迷宫的不同位置。求他们如果要相见，至少要穿过多少堵墙。保证任意两个圆不相交，不重合，也不会相切，但有可能相互包含。人的

一时失言乱红尘/ 2023年10月03日 19:28/ 0 赞/ 55 阅读

相关码蹄集直线

一、题目如果用数学的观点来简化这个世界，将人生看做一条直线，那么世界上的一些人注定和我们平行或者异面。由这种人生哲理，我们可以考虑一下瓜大的同学—共可能有多少种交点数量

男娘i/ 2023年10月03日 19:27/ 0 赞/ 57 阅读

相关直线的倾斜角斜率和直线方程

前言更新时间：2019-08-05 倾斜角斜率直线的倾斜角的范围\\(\\theta\\in \[0，\\pi)\\)； ![992978-20190

女爷i/ 2023年08月17日 17:32/ 0 赞/ 180 阅读

相关直线检测研究

直线检测： LSD ：http://www.ipol.im/pub/art/2012/gjmr-lsd/ 解读【1】论文回顾之一一种新的直线段检测[算法][Link

心已赠人/ 2022年06月09日 01:08/ 0 赞/ 226 阅读

相关 LSD直线检测

代码来源：[http://www.ipol.im/pub/art/2012/gjmr-lsd/][http_www.ipol.im_pub_art_2012_gjmr-lsd]

女爷i/ 2022年06月09日 01:00/ 0 赞/ 244 阅读

相关直线绘制算法

目录数值微分法中点画线法 Bresenham算法 -------------------- 三种常用直线绘制算法： 1）数值微分法（Digital

﹏ヽ暗。殇╰゛Y/ 2022年03月26日 05:24/ 0 赞/ 397 阅读

相关直线与圆

前言 > 当涉及直线与圆的相关问题时，考查最多的知识点是其中的\\(Rt\\triangle\\)。注：其中的\\(Rt\\triangle\\)指半弦长与半径和弦心距构

Myth丶恋晨/ 2021年12月23日 04:55/ 0 赞/ 394 阅读

相关 canvas绘制直线

说明： lineTo(x, y) 绘制一条从当前位置到指定x以及y位置的直线。 moveTo(x, y) 将笔移动到指定的坐标x以及y上。 s

迈不过友情╰/ 2021年07月24日 16:57/ 0 赞/ 553 阅读