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-12-24怎么切换 Git 项目的远程仓库地址?-icode9专业技术文章分享
- 2024-12-24怎么更改 Git 远程仓库的名称?-icode9专业技术文章分享
- 2024-12-24更改 Git 本地分支关联的远程分支是什么命令?-icode9专业技术文章分享
- 2024-12-24uniapp 连接之后会被立马断开是什么原因?-icode9专业技术文章分享
- 2024-12-24cdn 路径可以指定规则映射吗?-icode9专业技术文章分享
- 2024-12-24CAP:Serverless?+AI?让应用开发更简单
- 2024-12-23新能源车企如何通过CRM工具优化客户关系管理,增强客户忠诚度与品牌影响力
- 2024-12-23原创tauri2.1+vite6.0+rust+arco客户端os平台系统|tauri2+rust桌面os管理
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享