一眼看上去就应该能用半平面交去做。
首先考虑怎么求可能得第1名的人:每个人的函数为直线,就是在所有人的半平面交中的上边界者即可获得第一名,这个可以单调队列求解。
再考虑如何求可能得第2名的人:满足2个条件:1、在去掉可能得第1名的人后可以拿第1,这个跳转到上面的过程;2、至多同时被1个能拿第一名的人超越,这个应该在半平面上做一个区间覆盖,可以线段树或者二分求解,我懒得不会写线段树就只写了二分。
第3~m名,可以仿照第2名的过程,做m次半平面交,其实会m=2就是会正解了。
时间复杂度O(nmlogn)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int>pii;
const int N=1e5+;
struct node{
ll a,b,c;
node(){a=b=,c=;}
node(ll x,ll y){if(y<)x=-x,y=-y;a=x/y;b=x%y;c=y;if(b<)b+=c,a--;}
ll ceil(){return a+(b>);}
bool operator<(const node&t)const{return a==t.a?b*t.c<t.b*c:a<t.a;}
bool operator<=(const node&t)const{return a==t.a?b*t.c<=t.b*c:a<t.a;}
}p[N];
int n,m,top,tot,id[N],ans[N],st[N];
ll a[N],b[N];
pii s[N<<];
bool cmp(int x,int y){return a[x]<a[y]||a[x]==a[y]&&b[x]>b[y];}
node cross(int x,int y){return node(b[y]-b[x],a[x]-a[y]);}
void solve(int k)
{
top=tot=;
p[]=node(,);
for(int i=;i<=n;i++)
if(ans[id[i]]==-&&a[id[i]]>a[st[top]])
{
while(top&&cross(id[i],st[top]).a<p[top].ceil())top--;
st[++top]=id[i];
if(top>)p[top]=cross(st[top-],id[i]);
}
p[top+]=node(1ll<<,);
for(int i=;i<=n;i++)
if(ans[i]>)
{
int l=,r=top-,mid,pos=top;
while(l<=r)
{
mid=l+r>>;
if(a[st[mid]]>=a[i]||cross(st[mid],i)<=p[mid+])pos=mid,r=mid-;
else l=mid+;
}
s[++tot]=pii(a[st[pos]]>=a[i]?:cross(st[pos],i).a+,);
l=,r=top,pos=;
while(l<=r)
{
mid=l+r>>;
if(a[st[mid]]<=a[i]||p[mid]<=cross(st[mid],i))pos=mid,l=mid+;
else r=mid-;
}
if(a[st[pos]]>a[i])s[++tot]=pii(cross(st[pos],i).ceil(),-);
}
sort(s+,s+tot+);
for(int i=,j=,sum=;i<=top;i++)
{
while(j<=tot&&s[j].first<=p[i].ceil())sum+=s[j++].second;
if(sum<k)ans[st[i]]=k;
while(j<=tot&&s[j].first<=p[i+].a)
{
int p=j;
while(p<=tot&&s[p].first==s[j].first)sum+=s[p++].second;
if(sum<k)ans[st[i]]=k;
j=p;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]),id[i]=i,ans[i]=-;
sort(id+,id+n+,cmp);
for(int i=;i<=m;i++)solve(i);
for(int i=;i<=n;i++)printf("%d ",ans[i]);
}