#算法/线段树
#算法/快读
参考题解:
题解参考
这题思路:
先将坐标进行极角排序,按照顺时针的先后顺序,如果出现两个坐标在一个象限中,我们就先判断这两个坐标是否在同一条直线上,如果在同一条直线上,我们按照离原点最近的长度进行排序
之后,我们通过线段树的方法,定义结点tr[i]代表第i个结点区间离原点最短的距离,接着在定义l,r代表第l第r个坐标
在query里边,我们查找[l,r]范围内最先被木棍遍历到的点
query(int p,int l,int r,int x,int y,_int128 val);
在query函数中,我们先判断当前的l,r是否就是x,y,如果是x,y我们再判断l是否等于r
如果l等于r并且,距离<=val,返回下标l或者r,否则返回-1
如果l!=r,那么,我们先判断左半部分的最小值tr[lc]是否<=val,如果不等于,我们就直接return query(rc,mid,r,mid+1,y,_int128 val);
如果x,y不是l,r我们分成三部分讨论:
mid=l+r>>1;
1.x,y在l,r中间的左侧,y<=(l+r>>1),我们就返回l,r的左半部分
2.x,y在l,r中间右侧,x>=mid+1,我们就返回l,r的右半部分
3.x,y在mid两侧,我们就先判断左侧返回的是否是-1,如果是-1,返回右侧最小下标
在update里边,我们对单点修改,当我们找到一个可以被修改的点,我们就将这个点修改为INF
如果l==r直接修改tr[p]=INF,否则,左右分开讨论,pos在哪一半就修改哪一半,最终更新父节点pushUp( p)
在线段树以外,由于我们是_int128,因此我们还需要用到快读
#include <bits/stdc++.h>using namespace std;const int N=2e5+10;typedef long long ll;#define lc p<<1
#define rc p<<1|1const __int128 INF=1e37;struct point{ll x;ll y;ll z;int id;
}points[N];int n;
__int128 L;template<typename T>
inline T read(T&x){x=0;T f=1;char ch=getchar();if(ch=='-'){f=-1;ch=getchar();}while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch-'0');ch=getchar();}return x*f;
}__int128 tr[4*N];
int ans[N];int XiangXian(point p){if(p.x>=0&&p.y>0)return 1;if(p.x>0&&p.y<=0)return 2;if(p.x<=0&&p.y<0)return 3;
// if(p.x<0&&p.y>=0)return 4;else return 4;}ll cross(point p1,point p2){return p1.x*p2.y-p1.y*p2.x;
}bool cmp(point p1,point p2){if(XiangXian(p1)==XiangXian(p2)){if(cross(p1,p2)==0){return p1.x*p1.x+p1.y*p1.y<p2.x*p2.x+p2.y*p2.y;}else{return cross(p1,p2)<0;}}return XiangXian(p1)<XiangXian(p2);
}
void pushup(int p){tr[p]=min(tr[lc],tr[rc]);
}
void build(int p,int l,int r){if(l==r){tr[p]=points[l].x*points[l].x+points[l].y*points[l].y;return;}int mid=l+r>>1;build(lc,l,mid);build(rc,mid+1,r);pushup(p);
}int query(int p,int l,int r,int x,int y,__int128 len){if(l==x&&r==y){if(tr[p]>len)return -1;if(l==r){if(tr[p]>len)return -1;return l;}int mid=l+r>>1;if(tr[lc]<=len)return query(lc,l,mid,x,mid,len);else return query(rc,mid+1,r,mid+1,y,len);}int mid=l+r>>1;if(y<=mid)return query(lc,l,mid,x,y,len);if(x>mid)return query(rc,mid+1,r,x,y,len);else{int pos=query(lc,l,mid,x,mid,len);if(pos==-1){return query(rc,mid+1,r,mid+1,y,len);}return pos;}
}void update(int p,int l,int r,int pos,__int128 len){if(l==r){tr[p]=len;return;}int mid=l+r>>1;if(pos<=mid){update(lc,l,mid,pos,len);}else{update(rc,mid+1,r,pos,len);}pushup(p);
}int main(void){read(n);read(L);for(int i=1;i<=n;i++){cin>>points[i].x>>points[i].y>>points[i].z;points[i].id=i;}sort(points+1,points+1+n,cmp);build(1,1,n);int last=0;int lastrank=0;int rank=0;memset(ans,-1,sizeof ans);while(true){int idx=-1;if(last+1<=n){idx=query(1,1,n,last+1,n,L*L);if(idx!=-1){L+=points[idx].z;}}if(idx==-1){if(last>=2){idx=query(1,1,n,1,last-1,L*L);if(idx!=-1){L+=points[idx].z;}}}if(idx==-1)break;update(1,1,n,idx,INF);if(last==0){ans[points[idx].id]=++rank;last=idx;lastrank=rank; }else{if(XiangXian(points[last])==XiangXian(points[idx])&&cross(points[last],points[idx])==0){ans[points[idx].id]=lastrank;rank++;last=idx;}else{ans[points[idx].id]=++rank;lastrank=rank;last=idx;}}}for(int i=1;i<=n;i++){cout<<ans[i]<<" ";}return 0;
}
)