传送门
题解:
首先这道题是ZJOI2019里面idea最简单的题。
注意是idea最简单的题,也就是说六道题口胡起来最简单的是这道。那这道题凭什么放在D2T3?
凭它细节巨多。。。
来,先口胡正解做法。
按照斜率给所有直线排序,考虑从答案小的往答案大的处理,把已经得到答案的直线跳过剩下的直线拿来做半平面交,然后枚举所有已经得到答案的直线,考虑 处于什么区间的时候这条直线会让下面直线的排名+1,记录所有变化位置,扫描线,更新答案。
没了,思路就是这么简单,你让我再把思路讲详细点我也不知道该怎么讲。如果看不懂说明你的计算几何水平还没到能做这道题的程度
然后是细节。
首先是做半平面交时候的细节。
第一个细节,当交成下面这种情况的时候,三条线都要保留:
因为题目中排名的计算方式是“严格大于”,所以等于的情况不能够影响它的排名,但是按照一般半平面交的写法,这种情况是要弹掉的。。。
然后你看了一眼数据范围,这是一个开long double都会炸精度的范围,你并没有什么好的办法来处理这种情况。。。
于是你手写一个分数类,然后你发现它乘法爆long long 了,所以分数我们只能表示成 的形式。。。
第二个细节,交成下面这种情况中间那条线是要弹掉的:
注意这里实际上说的是中间那条线不能够在 为任何一个整数的时候成为最大值。
但是本题要求的 必须是一个非负整数,所以中间那条线现在已经就宣告gg了
既然要求 是一个非负整数,那么新的直线与原来直线的交点到了 负半轴是需要把栈弹完的。
其实不容易注意到的细节就前面两个,剩下的就是二分找到之前已经确定了答案的直线的影响范围。这个其实还好,注意一下边界,根据选择记录开区间还是闭区间,细节有所不同也不是很好说清楚,只有自己注意了。
具体实现不建议用任何实数类型,其实封装一个简易的带分数类型是可以做到的,因为只有赋值和比较,没有带分数之间的运算。
代码:
#include<bits/stdc++.h>
#define ll long long
#define re register
#define cs const
namespace IO{
inline char gc(){
static cs int Rlen=1<<22|1;
static char buf[Rlen],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline T get(){
char c;T num;
while(!isdigit(c=gc()));num=c^48;
while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48);
return num;
}
inline int gi(){return get<int>();}
inline ll gl(){return get<ll>();}
}
using namespace IO;
using std::cerr;
using std::cout;
using pli=std::pair<ll,int>;
#define fi first
#define se second
cs int N=1e5+7;
struct frac{
ll a,b,c;//a + b/c (c>0,b>0)
frac(){a=b=0,c=1;}
frac(ll x,ll y){
if(y<0)x=-x,y=-y;
a=x/y,c=y,b=x%y;
if(b<0)b+=c,--a;
}
ll flr()cs{return a;}
ll cel()cs{return a+(b>0);}
bool operator<(cs frac &x)cs{return a==x.a?b*x.c<x.b*c:a<x.a;}
bool operator<=(cs frac &x)cs{return a==x.a?b*x.c<=x.b*c:a<=x.a;}
};
int n,m,ct,tp;
int id[N],st[N],ans[N];
ll a[N],b[N];frac x[N];
pli q[N<<1];
inline frac gx(int x,int y){
return frac(b[x]-b[y],a[y]-a[x]);
}
inline void solve(int k){
ct=tp=0;x[0]=frac(0,1);
for(int re i=1;i<=n;++i)if(-1==ans[id[i]]&&a[id[i]]>a[st[tp]]){
int u=id[i];
while(tp&&gx(u,st[tp]).flr()<x[tp].cel())--tp;
st[++tp]=u;if(tp>1)x[tp]=gx(u,st[tp-1]);
}
x[tp+1]=frac(1ll<<60,1);
for(int re i=1;i<=n;++i)if(~ans[i]){
int l=1,r=tp-1,t=tp;
while(l<=r){
int mid=l+r>>1;
if(a[st[mid]]>=a[i]||gx(st[mid],i)<=x[mid+1])t=mid,r=mid-1;
else l=mid+1;
}
q[++ct]=pli(a[st[t]]>=a[i]?0ll:gx(st[t],i).flr()+1,1);
l=2,r=tp,t=1;
while(l<=r){
int mid=l+r>>1;
if(a[st[mid]]<=a[i]||x[mid]<=gx(st[mid],i))t=mid,l=mid+1;
else r=mid-1;
}
if(a[st[t]]>a[i])q[++ct]=pli(gx(st[t],i).cel(),-1);
}
std::sort(q+1,q+ct+1);
for(int re i=1,j=1,p=0;i<=tp;++i){
while(j<=ct&&q[j].fi<=x[i].cel())p+=q[j++].se;
if(p<k)ans[st[i]]=k;
while(j<=ct&&q[j].fi<=x[i+1].flr()){
int l=j;while(l<=ct&&q[l].fi==q[j].fi)p+=q[l++].se;
if(p<k)ans[st[i]]=k;j=l;
}
}
}
signed main(){
#ifdef zxyoi
freopen("ZJOI.in","r",stdin);
#endif
n=gi(),m=gi();
for(int re i=1;i<=n;++i)
a[i]=gl(),b[i]=gl(),id[i]=i,ans[i]=-1;
std::sort(id+1,id+n+1,[](int x,int y){
return a[x]<a[y]||(a[x]==a[y]&&b[x]>b[y]);
});
for(int re i=1;i<=m;++i)solve(i);
for(int re i=1;i<=n;++i)cout<<ans[i]<<" ";
return 0;
}
转载:https://blog.csdn.net/zxyoi_dreamer/article/details/102487964