CF1163C1 Power Transmission (Easy Edition) 题解

· · 题解

前言

再没见过这么水的 *1900 了……

附：做完这题可以去做一下 [ABC248E] K-colinear Line。

解法

首先，两条直线如果能相交，那么它们的斜率必然不相等。

所以，我们只需要枚举每两个点，然后将经过它们的直线的斜率存进一个 std::vector，最后直线两两再枚举判断斜率是否相等即可。

但是，本题需要处理三点共线。

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

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

每次枚举两个点的时候，就把其他所有点都扫一遍，每遇到一个新的点，如果它与原始的两个点贡献，那么将它装入数组 v。最后给 v 中的数两两打上标记，下次再枚举到就可以直接跳过。

放代码：

#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
typedef pair<int,int> pii;
bool pd(pii a,pii b,pii c){
  return (b.nd-a.nd)*(c.st-a.st)==(b.st-a.st)*(c.nd-a.nd);
} // 判断函数
int main(){
  ios::sync_with_stdio(false);
  int n,c=0; cin>>n;
  vector<pii> a(n),d;
  vector<vector<bool> > b(n,vector<bool>(n));
  for(auto &[x,y]:a)cin>>x>>y;
  for(int i=0;i<n-1;i++)
    for(int j=i+1;j<n;j++){
      if(b[i][j])continue;
      vector<int> v={i,j};
      for(int k=j+1;k<n;k++)
        if(pd(a[i],a[j],a[k]))v.emplace_back(k); // 统计三点共线
      for(auto &i:v)for(auto &j:v)b[i][j]=true; // 打标记
      d.emplace_back(a[i].st-a[j].st,a[i].nd-a[j].nd);
    }
  for(auto &i:d)for(auto &j:d)
    c+=(i.st*j.nd!=i.nd*j.st); // 枚举斜率不相同的直线有多少对
  cout<<(c>>1)<<endl; // 每两个点统计了两遍，最终答案需要除以二
  return 0;
}