Time Limit: 1 second

Memory Limit: 32 MB

【问题描述】

平面上有n条直线，且无三线共点，问这些直线能有多少种不同的交点数。

【输入格式】

n(n≤20)

【输出格式】

若干行，列出所有相交方案，其中每一行为一个可能的交点数。

【输入样例】

4

【输出样例】

0

3

4

5

6

(表示4条直线的情况下，可能有0、3、4、5、6个交点)

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=a401

【题解】



1条直线的话交点为0；

2条直线交点为1或0；

3条直线的话交点为0，2,3;

4条直线:

①4条直线都平行，交点数为0

②3条直线平行，剩下一条和这3条都相交，交点数为3；

④2条直线平行，则剩下两条直线和这两条平行直线都有交点2*2=4;但是剩下的这两条直线情况未知,是相交还是平行?可以注意到这时又转换成2条直线的问题了；即交点数为2*2+f(2);其中f(x)表示x条直线能够产生多少个交点;

⑤3条直线平行，则剩下一条直线和这3条直线都有交点1*3=3;剩下一条直线；则可以写成1*3+f(1);

综上我们枚举n条直线有j条平行线，则答案就为(n-j)*j+f(n-j);

设bo[x][y]表示x条直线y个交点的情况是否存在

    bo[1..n][0]=true

    rep1(i,2,n)//枚举有几条直线

        rep1(j,1,i)//枚举它有几条平行线;

        {

            int a = j,b = i-j;//b为未知直线

            rep1(k,0,MAXN2-1)//我们相当于在枚举f(i-j)的可能值

                if (bo[b][k])//如果i-j条直线可能有k个交点

                    bo[i][k+b*a] = true;//a*b是平行线和未知直线的交点(肯定是有这些交点的)而k是i-j条线自己内部的交点;

        }

【完整代码】

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <set>

#include <map>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <queue>

#include <vector>

#include <stack>

#include <string>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

void rel(LL &r)

{

    r = 0;

    char t = getchar();

    while (!isdigit(t) && t!='-') t = getchar();

    LL sign = 1;

    if (t == '-')sign = -1;

    while (!isdigit(t)) t = getchar();

    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();

    r = r*sign;

}

void rei(int &r)

{

    r = 0;

    char t = getchar();

    while (!isdigit(t)&&t!='-') t = getchar();

    int sign = 1;

    if (t == '-')sign = -1;

    while (!isdigit(t)) t = getchar();

    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();

    r = r*sign;

}

const int MAXN = 25;

const int MAXN2 = 200+10;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

int n;

bool bo[MAXN][MAXN2];

bool flag[MAXN];

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    memset(bo,false,sizeof(bo));

    rei(n);

    rep1(i,0,n)

        bo[i][0] = true;

    rep1(i,2,n)

        rep1(j,1,i)

        {

            int a = j,b = i-j;

            rep1(k,0,MAXN2-1)

                if (bo[b][k])

                    bo[i][k+b*a] = true;

        }

    rep1(i,0,MAXN2-1)

    if (bo[n][i])

        printf("%d\n",i);

    return 0;

}