2021“MINIEYE杯”中国大学生算法设计超级联赛(3) 1004.Game on Plane (思维)
2021/7/28 14:05:48
本文主要是介绍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; }
这篇关于2021“MINIEYE杯”中国大学生算法设计超级联赛(3) 1004.Game on Plane (思维)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-25初学者必备:订单系统资料详解与实操教程
- 2024-12-24内网穿透资料入门教程
- 2024-12-24微服务资料入门指南
- 2024-12-24微信支付系统资料入门教程
- 2024-12-24微信支付资料详解:新手入门指南
- 2024-12-24Hbase资料:新手入门教程
- 2024-12-24Java部署资料
- 2024-12-24Java订单系统资料:新手入门教程
- 2024-12-24Java分布式资料入门教程
- 2024-12-24Java监控系统资料详解与入门教程