[ABC248E] K-colinear Line 题解

FFTotoro · 2022-10-21 16:25:37 · 题解

本题要求确定一共有多少条直线至少经过了 K 个点。

所以，我们首先需要一个判断三点共线的函数；利用相似三角形的原理即可。

bool pd(int a,int b,int c){
  return (ay[b]-ay[a])*(ax[c]-ax[a])==(ax[b]-ax[a])*(ay[c]-ay[a]);
}

于是，我们可以使用枚举部分时间复杂度为 O(n^3)，标记部分时间复杂度 O(n^4) 的的做法：

先枚举两个点（两点确定一条直线），然后再在其它点中看有没有和这两个点共线的。然后统计一下这条直线上一共有多少个点，如果点数大于或等于K 那么答案就加一。

注意，如果一条直线统计完，需要给这条直线中的每两个点打上已判定的标记，避免重复的统计。

本题需要一个特判：如果 K=1，那么显然有无数条直线满足要求，输出 Infinity 即可。

核心代码：

for(int i=1;i<n;i++)
  for(int j=i+1;j<=n;j++)
    if(!f[i][j]){
      vector<int> v={i,j};
      for(int x=j+1;x<=n;x++)
        if(pd(i,j,x))v.emplace_back(x);
      for(int x=0;x<v.size()-1;x++)
        for(int y=x+1;y<v.size();y++)
          f[v[x]][v[y]]=true;
      if(v.size()>=k)c_all++;
    }