镇江市建设工程安全监督站网站,建设班级网站首页,网站建设的实验步骤,北京电力交易中心公示题目链接#xff1a;P8777 [蓝桥杯 2022 省 A] 扫描游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 样例输入#xff1a;
5 2
0 1 1
0 3 2
4 3 5
6 8 1
-51 -33 2
样例输出#xff1a;
1 1 3 4 -1
分析#xff1a;先考虑如何对物件进行排序#xff0c;首先…题目链接P8777 [蓝桥杯 2022 省 A] 扫描游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 样例输入
5 2
0 1 1
0 3 2
4 3 5
6 8 1
-51 -33 2
样例输出
1 1 3 4 -1
分析先考虑如何对物件进行排序首先因为我们需要按序考虑该物件是否能被碰到这个可以先对每个点进行象限划分然后对于不同象限的我们可以直接进行排序对于同一象限内的点我们可以通过叉积来判断先后顺序叉积的正负代表了旋转的方向所以这样我们就可以对所有的点进行排序。
排完序我们就可以来求在当前状态下下一个能够碰到的物件的编号这个我们可以用线段树那么就是每次找寻一个区间内第一个到原点距离小于等于当前棒长度的物件这个我们可以用线段树二分去寻找假如当前所在的物件是now那么我们首先去物件编号为now1~n的物件里面去寻找是否有小于等于当前棒长度的物件如果有的话就更新当前棒的长度然后把这个物件的距离设置为无穷大。如果没有的话就去物件编号为1~now-1的物件里面去寻找同理有的话就对棒的长度进行修改。如果两个区间都没有找到那么说明所有的物件都不可能再被碰到那么也就终止了。
但不知道为什么洛谷上是有一个点过不了的但是其他平台可过希望有大佬能指出错误
#includecstdio
#includeiostream
#includealgorithm
#includecstring
#includemap
#includequeue
#includevector
#includecmath
using namespace std;
typedef long long ll;
const int N1e610;
int l[N],r[N];
long long mn[N];
int ans[N];
struct node{int id;ll x,y,z;
}p[N];
int find(node a)//判断该点属于哪一象限
{if(a.x0a.y0) return 1;else if(a.x0a.y0) return 2;else if(a.x0a.y0) return 3;else return 4;
}
ll mul(node a,node b)//求叉积
{return a.x*b.y-a.y*b.x;
}
bool cmp(node a,node b)
{if(find(a)!find(b)) return find(a)find(b);if(mul(a,b)0) return a.x*a.xa.y*a.yb.x*b.xb.y*b.y;return mul(a,b)0;
}
void pushup(int id)
{mn[id]min(mn[id1],mn[id1|1]);
}
void build(int id,int L,int R)
{l[id]L;r[id]R;mn[id]0x3f3f3f3f3f3f3f3f;if(LR){mn[id](int)sqrt(1.0*p[L].x*p[L].xp[L].y*p[L].y);if(mn[id]*mn[id]!p[L].x*p[L].xp[L].y*p[L].y) mn[id];return ;}int midLR1;build(id1,L,mid);build(id1|1,mid1,R);pushup(id);return ;
}
void update_point(int id,int pos,long long val)
{if(l[id]r[id]){mn[id]val;return ;}int midl[id]r[id]1;if(posmid) update_point(id1,pos,val);else update_point(id1|1,pos,val);pushup(id);
}
void query_interval(int id,int L,int R,ll val,int pos)//在区间[L,R]中找寻第一个小于等于val的编号
{if(pos) return ;if(l[id]r[id]){posl[id];return ;}int midl[id]r[id]1;if(midLmn[id1]val) query_interval(id1,L,R,val,pos);if(pos) return ;if(mid1Rmn[id1|1]val) query_interval(id1|1,L,R,val,pos);return ;
}
int main()
{ll n,L;cinnL;for(int i1;in;i){p[i].idi;scanf(%lld%lld%lld,p[i].x,p[i].y,p[i].z);if(p[i].x0p[i].y0) Lp[i].z,p[i].xp[i].y0x3f3f3f3f;}sort(p1,pn1,cmp);build(1,1,n);int now0;int rank1,cnt0;//rank记录当前应该分配的排名cnt记录当前同排名的人数node last;//记录上一个排名 while(true){int pos0;if(now!n){query_interval(1,now1,n,L,pos);if(pos){Lp[pos].z;if(rank1cnt0){cnt;ans[p[pos].id]rank;}else{if(find(last)find(p[pos])mul(last,p[pos])0){cnt;ans[p[pos].id]rank;}else{rankcnt;ans[p[pos].id]rank;cnt1;}}lastp[pos];nowpos;update_point(1,pos,0x3f3f3f3f3f3f3f3f); continue;}}if(now!1now){query_interval(1,1,now-1,L,pos);if(pos){Lp[pos].z;if(rank1cnt0){cnt;ans[p[pos].id]rank;}else{if(find(last)find(p[pos])mul(last,p[pos])0){cnt;ans[p[pos].id]rank;}else{rankcnt;ans[p[pos].id]rank;cnt1;}}lastp[pos];nowpos;update_point(1,pos,0x3f3f3f3f3f3f3f3f); continue;}}break;}for(int i1;in;i)if(ans[i]) printf(%d ,ans[i]);else printf(-1 );return 0;
}
