题解：AT_abc248_e [ABC248E] K-colinear Line

AK_lwh_888 · 2024-11-20 17:41:59 · 题解

题意

题目让我们求出在一个用直线连接各个坐标的点，算起来一共需要连接 k 个点，直线至少的根数。但是，如果根数是无限的，也就是错误的，这个时候我们需要输出 Infinity。

题解

这道题我们可以用 dfs 来循环遍历，看至少的根数。开始时它是有 n 个点，需要我们用直线任意连接其中 k 个点，因为题目中说在平面直角坐标系上的点，所以我们可以用个二维的 bool 数组来存储一下那 n 个点。也就是下面的代码：

for(int i=1;i<=n;++i){
    cin>>x[i]>>y[i];
    vis[x[i]][y[i]]=true;
}

然后就是 dfs 的写法。题目是让我们画直线的，所以我们可以在 dfs 中可以直接模拟一下直线。在这里可以用变向数组来化简一下。

数组里面存的，就是我们循环嵌套里面要走的方向。

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

当 dfs 开始的时候，我们要用两个变量将现在的两个坐标存起来，不然在后面的时候我们要修改坐标，不可能把现在的坐标给修改了。然后就是在每一次要变换方向的时候，都要将这两个表示坐标的变量给初始化一下，不然就会出现很严重的错误。还有，当每次到达一个点的时候，直线条数要加上 1。

如下：

void dfs(int xz,int yz){
    int x2=xz,y2=yz; 
    for(int i=0;i<4;++i){
        x2=xz,y2=yz; 
        for(int j=xz;j<=300;++j){
            for(int v=yz;v<=300;++v){
                if(vis[x2][y2]==true){
                    dfs(j,v);
                    ans++;
                }
                x2+=dx[i],y2+=dy[i];
            }
        }
    }
}

code

#include<bits/stdc++.h>
using namespace std;
const int N=301;
int n,k,x[N],y[N],ans=0;
bool vis[N][N]={false};
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
void dfs(int xz,int yz){
    int x2=xz,y2=yz; 
    for(int i=0;i<4;++i){
        x2=xz,y2=yz; 
        for(int j=xz;j<=300;++j){
            for(int v=yz;v<=300;++v){
                if(vis[x2][y2]==true){
                    dfs(j,v);
                    ans++;
                }
                x2+=dx[i],y2+=dy[i];
            }
        }
    }
}
signed main(){
    cin>>n>>k;
    if(k==1){
        cout<<"Infinity\n";
        return 0;
    }
    for(int i=1;i<=n;++i){
        cin>>x[i]>>y[i];
        vis[x[i]][y[i]]=true;
    }
    dfs(x[1],y[1]);
    printf("%d\n",ans);
    return 0;
}