题解：P10907 [蓝桥杯 2024 国 B] 蚂蚁开会

Sweet_2013 · 2024-12-29 01:22:55 · 题解

暴力解法是：三层循环，遍历所有可能的点，每个点逐个判断是否有超过两个线段经过，然后记录个数。时间复杂度 O(mx\times my\times n)。

正解是这样的：

• 不再遍历所有可能点，而是遍历每条线段上的整数点。
• 将其出现的次数存到哈希表中。
• 遍历哈希表统计交点的数量。此时的时间复杂度最坏 O(n\times \max(x,y))。

  #include<bits/stdc++.h>
  using namespace std;
  typedef pair<int, int> PII;
  int n, m, ux[501], uy[501], vx[501], vy[501], ans;
  map<PII, int> cnt_mp;
  int gcd(int a, int b){return b?gcd(b,a%b):a;}
  void count(int i){
  int x1=ux[i], x2=vx[i], y1=uy[i], y2=vy[i], dx=x2-x1, dy=y2-y1, d=gcd(abs(dx),abs(dy));
  dx/=d;
  dy/=d;
  for (int i=0; ;i++) {
      int x=x1+i*dx, y=y1+i*dy;
      cnt_mp[{x, y}]++;   
      if (x==x2&&y==y2) break;
  }
  }
  int main(){
  cin >> n;
  for (int i=0;i<n;i++) {
      cin >> ux[i]>> uy[i]>> vx[i]>> vy[i];
      count(i);
  }
  for (map<PII, int>::iterator it = cnt_mp.begin(); it != cnt_mp.end(); it++) if (it->second >= 2) ans++;
  cout <<ans<< endl;
  return 0;
  }