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肯定要选平行最多的直线画一条和它们斜率相同的直线,那么也就不难想到A的选法一定是在各个斜率循环跑,具体实现过程就是将各个斜率按直线数排序,从最大的开始跑即可.

  • 代码

    #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;
    }
    
上一篇:AT2667-[AGC017D]Game on Tree【SG函数】


下一篇:【题解】CF1539E Game with Cards