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-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望