hdu 1466 计算直线的交点数 递推

时间：2023-03-10 07:22:45
hdu 1466 计算直线的交点数 递推
题目描述

平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。
比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。

输入

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

输出

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

样例输入
2

3
样例输出
0 1

0 2 3

题解：我们可以从n-1条直线相交的情况推导出n条直线的相交情况，考虑到直线的关系不是相交就是平行，我们可以推倒一下n=4的情况：

　　已知n=3时有0,2,3;

　　(1):第四条直线与前三条平行，则有0;

　　(2):第四条直线与其中两条平行，则有3;

　　(3):第四条直线与其中一条平行，则有4,5;

　　(4):第四条直线不与任何直线平行，则有3,5,6;

　　大致可以知道当有j条边与第n条直线不平行是时候有（n-j）*j加上j条直线的交点，

　　得出状态dp[j][j条边的交点]存在，得出状态dp[n][(n-j)*j+j条直线的交点]存在

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <vector>

#include <cstdlib>

#include <iomanip>

#include <cmath>

#include <ctime>

#include <map>

#include <set>

using namespace std;

#define lowbit(x) (x&(-x))

#define max(x,y) (x>y?x:y)

#define min(x,y) (x<y?x:y)

#define MAX 100000000000000000

#define MOD 1000000007

#define pi acos(-1.0)

#define ei exp(1)

#define PI 3.141592653589793238462

#define INF 0x3f3f3f3f3f

#define mem(a) (memset(a,0,sizeof(a)))

typedef long long ll;

ll gcd(ll a,ll b){

    return b?gcd(b,a%b):a;

}

bool cmp(int x,int y)

{

    return x>y;

}

//const int N=10005;

const int mod=1e9+;

#define N 200//当n=20的时候交点数目最多为n*(n-1)/2 < 200

int dp[][N];//dp[直线的总数][交点的个数] = 状态（本状态存在为1，否则为0）

int main ()

{

    int i,n,j,k;

    for (i=;i<;i++)

        dp[i][]=;//所有的直线都平行

    for (i=;i<;i++)//枚举n的值，并且打标

        for (j=;j<i;j++)//枚举与i相交的边的数目

            for (k=;k<N;k++)//枚举j条边的交点情况

                if (dp[j][k])//如果存在则推论成功

                    dp[i][(i-j)*j+k] = ;

    while(cin>>n){

        for(i=;i<N;i++){

            if(dp[n][i]){

                if (i) cout<<" ";

                cout<<i;

            }

        }

        cout<<endl;

    }

    return ;

}

相关文章