-
题意:有\(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; }
相关文章
- 10-242021“MINIEYE杯”中国大学生算法设计超级联赛(8)1008. Square Card(计算几何)
- 10-24HDU7084/2021“MINIEYE杯”中国大学生算法设计超级联赛(10)1008. Pty loves string(Border/KMP Fail树/DFS序/主席树)
- 10-242021“MINIEYE杯”中国大学生算法设计超级联赛(5)题解
- 10-242021“MINIEYE杯”中国大学生算法设计超级联赛 第九场题解
- 10-242021“MINIEYE杯”中国大学生算法设计超级联赛(3)题解
- 10-242021“MINIEYE杯”中国大学生算法设计超级联赛(1)部分题解
- 10-242021“MINIEYE杯”中国大学生算法设计超级联赛 第三场 赛后总结
- 10-24hdu 6975/ 2021“MINIEYE杯”中国大学生算法设计超级联赛(3)1003 Forgiving Matching(FFT)
- 10-24hdu7047 /2021“MINIEYE杯”中国大学生算法设计超级联赛(7) 1004 Link with Balls
- 10-242021“MINIEYE杯”中国大学生算法设计超级联赛(1)1008 Maximal submatrix