2021“MINIEYE杯”中国大学生算法设计超级联赛（3） 1004.Game on Plane (思维)

本文主要是介绍2021“MINIEYE杯”中国大学生算法设计超级联赛（3） 1004.Game on Plane (思维)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

• 题意：有\(n\)条直线，A每次选\(1,2,...,n\)条直线，B每次画一条直线，答案是B画的直线和A选的直线的相交数，现在A想要最大化答案，B想要最小化答案，问每次选\(1,2,...,n\)条直线的答案是多少.

• 题解：首先能想到的是A肯定要选彼此不平行的直线，B肯定要选平行最多的直线画一条和它们斜率相同的直线，那么也就不难想到Ａ的选法一定是在各个斜率循环跑，具体实现过程就是将各个斜率按直线数排序，从最大的开始跑即可．

• 代码：

  #include <bits/stdc++.h>
  #define ll long long
  #define fi first
  #define se second
  #define pb push_back
  #define me memset
  #define rep(a,b,c) for(int a=b;a<=c;++a)
  #define per(a,b,c) for(int a=b;a>=c;--a)
  const int N = 1e6 + 10;
  const int mod = 1e9 + 7;
  const int INF = 0x3f3f3f3f;
  using namespace std;
  typedef pair<int,int> PII;
  typedef pair<ll,ll> PLL;
  ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
  ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
  
  int n;
  struct Node{
      int ax,ay;
      int bx,by;
  }pt[N];
  
  int main() {
      ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
      int _;
      cin>>_;
      while(_--){
          cin>>n;
          map<PII,int> mp;
          rep(i,1,n){
              cin>>pt[i].ax>>pt[i].ay>>pt[i].bx>>pt[i].by;
              int x=pt[i].bx-pt[i].ax;
              int y=pt[i].by-pt[i].ay;
              int d=gcd(x,y);
              if(x==0) mp[make_pair(1,0)]++;
              else if(y==0) mp[make_pair(0,1)]++;
              else mp[make_pair(x/d,y/d)]++;
          }
          vector<int> v;
          for(auto w:mp){
              v.pb(w.se);
          }
          sort(v.begin(),v.end());
          int st=0;
          int mx=(int)v.size();
          mx--;
          int cur=mx;
          int ans=0;
          rep(i,1,n){
              if(v[cur]==0){
                  st++;
                  cur=mx;
              }
              if(cur!=mx) ans++;
              v[cur]--;
              cur--;
              if(cur<st) cur=mx;
              cout<<ans<<'\n';
          }
      }
  
  
      return 0;
  }
  

这篇关于2021“MINIEYE杯”中国大学生算法设计超级联赛（3） 1004.Game on Plane (思维)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！