【a401】直线的交点数

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;
}