（蓝桥真题）扫描游戏（计算几何+线段树二分）

题目链接：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，那么我们首先去物件编号为now+1~n的物件里面去寻找是否有小于等于当前棒长度的物件，如果有的话就更新当前棒的长度，然后把这个物件的距离设置为无穷大。如果没有的话就去物件编号为1~now-1的物件里面去寻找，同理，有的话就对棒的长度进行修改。如果两个区间都没有找到，那么说明所有的物件都不可能再被碰到，那么也就终止了。

但不知道为什么洛谷上是有一个点过不了的，但是其他平台可过，希望有大佬能指出错误！

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e6+10;
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.x>=0&&a.y>0) return 1;else if(a.x>0&&a.y<=0) return 2;else if(a.x<=0&&a.y<0) 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.x+a.y*a.y<b.x*b.x+b.y*b.y;return mul(a,b)<0;
}
void pushup(int id)
{mn[id]=min(mn[id<<1],mn[id<<1|1]);
}
void build(int id,int L,int R)
{l[id]=L;r[id]=R;mn[id]=0x3f3f3f3f3f3f3f3f;if(L==R){mn[id]=(int)sqrt(1.0*p[L].x*p[L].x+p[L].y*p[L].y);if(mn[id]*mn[id]!=p[L].x*p[L].x+p[L].y*p[L].y) mn[id]++;return ;}int mid=L+R>>1;build(id<<1,L,mid);build(id<<1|1,mid+1,R);pushup(id);return ;
}
void update_point(int id,int pos,long long val)
{if(l[id]==r[id]){mn[id]=val;return ;}int mid=l[id]+r[id]>>1;if(pos<=mid) update_point(id<<1,pos,val);else update_point(id<<1|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]){pos=l[id];return ;}int mid=l[id]+r[id]>>1;if(mid>=L&&mn[id<<1]<=val) query_interval(id<<1,L,R,val,pos);if(pos) return ;if(mid+1<=R&&mn[id<<1|1]<=val) query_interval(id<<1|1,L,R,val,pos);return ;
}
int main()
{ll n,L;cin>>n>>L;for(int i=1;i<=n;i++){p[i].id=i;scanf("%lld%lld%lld",&p[i].x,&p[i].y,&p[i].z);if(p[i].x==0&&p[i].y==0) L+=p[i].z,p[i].x=p[i].y=0x3f3f3f3f;}sort(p+1,p+n+1,cmp);build(1,1,n);int now=0;int rank=1,cnt=0;//rank记录当前应该分配的排名，cnt记录当前同排名的人数node last;//记录上一个排名 while(true){int pos=0;if(now!=n){query_interval(1,now+1,n,L,pos);if(pos){L+=p[pos].z;if(rank==1&&cnt==0){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{rank+=cnt;ans[p[pos].id]=rank;cnt=1;}}last=p[pos];now=pos;update_point(1,pos,0x3f3f3f3f3f3f3f3f); continue;}}if(now!=1&&now){query_interval(1,1,now-1,L,pos);if(pos){L+=p[pos].z;if(rank==1&&cnt==0){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{rank+=cnt;ans[p[pos].id]=rank;cnt=1;}}last=p[pos];now=pos;update_point(1,pos,0x3f3f3f3f3f3f3f3f); continue;}}break;}for(int i=1;i<=n;i++)if(ans[i]) printf("%d ",ans[i]);else printf("-1 ");return 0;
}