计算几何(二维数点问题)
2022/5/3 23:17:54
本文主要是介绍计算几何(二维数点问题),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
L. Light of Stars
题解:题目比较明显的提示了二维数点,关键在于坐标的变换的推导,感觉是正常高中水平就可以推出,所以不在题解里赘述了(其实是画图太麻烦,懒的画)
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<b;i++) #define pb push_back #define db double #define ll long long #define fi first #define se second #define all(x) x.begin(),x.end() const db pi = acos(-1.0); const int N = 1e5+5; double eps = 1e-8; vector<pair<db,db> > point; struct Node{ db fi,se; int id; }; vector<Node> pt; vector<db> V; int res[N]; int C[N]; int lowbit(int x){return x&(-x);} int query(int x){ int t = 0; for(;x;x -= lowbit(x))t += C[x]; return t; } void mofidy(int x,int d){ for(;x<N;x+=lowbit(x))C[x]+=d; return; } int discrete(db x){ return lower_bound(all(V),x) - V.begin() + 1; } int main(){ int n,k; scanf("%d%d",&n,&k); point.resize(n); pt.resize(n); rep(i,0,n)scanf("%lf%lf",&point[i].fi,&point[i].se); while(k--){ V.clear(); memset(C,0,sizeof C); db l,r;scanf("%lf%lf",&l,&r); db sl = sinl(l/180.0*pi), cl = cosl(l/180.0*pi); db sr = sinl(r/180.0*pi), cr = cosl(r/180.0*pi); rep(i,0,n){ db & x = point[i].fi; db & y = point[i].se; pt[i].fi = x * sr + y * cr; pt[i].se = x * sl + y * cl; pt[i].id = i; V.pb(pt[i].se); } sort(all(V)); V.erase(unique(all(V),[&](db a,db b){return fabs(a-b) <= eps;}),V.end()); sort(all(pt),[&](Node a ,Node b){ return fabs(a.fi-b.fi)>eps?a.fi<b.fi:a.se>b.se; }); rep(i,0,n){ int yy = discrete(pt[i].second-eps); res[pt[i].id] += query(N-1) - query(yy-1); mofidy(yy,1); } } rep(i,0,n){ printf("%d ",res[i]); } printf("\n"); }
这篇关于计算几何(二维数点问题)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行