2019ICPC沈阳站 E Capture Stars
2022/1/1 23:11:48
本文主要是介绍2019ICPC沈阳站 E Capture Stars,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Capture Stars
圆的反演
#pragma GCC optimize(3) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << "\n"; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //head const int N = 1e4 + 10; const double eps = 1e-6; int T, n, R, r; double x[N], y[N]; pdd seg[N]; inline void InvPoint(double &x, double &y) { double d = x*x+y*y; x = (4.0*R*R)/d*x; y = (4.0*R*R)/d*y; } int main() { scanf("%d", &T); while(T--) { scanf("%d %d %d", &n, &R, &r); for (int i = 1; i <= n; ++i) scanf("%lf %lf", &x[i], &y[i]); double fR = 2*R, fr = (4.0*R*R)/(2.0*r), m = (fR+fr)/2, mr = (fr-fR)/2; for (int i = 1; i <= n; ++i) { InvPoint(x[i], y[i]); double dx = fabs(x[i]-m); double dy = sqrt(mr*mr-dx*dx); seg[i].fi = y[i]-dy; seg[i].se = y[i]+dy; } sort(seg+1, seg+1+n); priority_queue<double, vector<double>, greater<double> > q; q.push(seg[1].se); int ans = 1; for (int i = 2; i <= n; ++i) { while(!q.empty() && q.top() < seg[i].fi + eps) { q.pop(); } q.push(seg[i].se); ans = max(ans, (int)q.size()); } printf("%d\n", ans); } return 0; }
这篇关于2019ICPC沈阳站 E Capture Stars的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain