题解 P6290 【[eJOI2017]粒子】

· · 题解

每次操作时二分，判断此时跑到最右的 x 粒子是否在跑到最左的 y 粒子右边。模拟 k 次即可。

由于我相信 O(nk\log n) 不能过，我们要接着优化。

其实就是求个半平面交的事。每次重构半平面交，然后把两边的上半部分分段加起来，在上面判断。

由于直线就那么几条，所以不用每次排序。

时间复杂度 O(n\log n+nk)。

然后当我发现评测记录里一大堆 0.9s+ 的时候心态就崩了。

第二天我过来补代码，补着补着发现时限甚至变成了 2s，然后提交记录前几个 1.8s+。看起来就是暴力常数太大然后申请开大时限。

然后开始无 能 狂 怒。是真的无能，由于一些原因当时发不了犇犇和帖子，连博客都不能发。

然而改时限其实很没道理，因为官方题解也说了 O(nk\log n) 可以过，当时也没什么卡常迹象，原则上场上能过的在这里也应该给过。所以我就只能干难受了

拿了个最优解不亏

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=50050,mod=998244353;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
    char ch=getchar();ll x=0,f=0;
    while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
struct line{
    int k,id1,id2;
    ll b;
    bool operator<(const line &l)const{
        if(k!=l.k) return k<l.k;
        return b>l.b;
    }
}lx[maxn],ly[maxn],hx[maxn],hy[maxn],h[maxn*2];
int n,l,k,tx[maxn],vx[maxn],ty[maxn],vy[maxn],tpx,tpy,tot;
inline double interx(line l1,line l2){
    return 1.0*(l1.b-l2.b)/(l2.k-l1.k);
}
line merge(line l1,line l2){
    return (line){l1.k+l2.k,l1.id1,l2.id1,l1.b+l2.b};
} 
int main(){
    n=read();l=read();k=read();
    FOR(i,1,n) tx[i]=read(),vx[i]=read(),lx[i]=(line){vx[i],i,0,-1ll*vx[i]*tx[i]};
    FOR(i,1,n) ty[i]=read(),vy[i]=read(),ly[i]=(line){vy[i],i,0,-1ll*vy[i]*ty[i]};
    sort(lx+1,lx+n+1);sort(ly+1,ly+n+1);
    while(k--){
        tpx=0;
        FOR(i,1,n){
            if(tpx && lx[i].k==hx[tpx].k) continue;
            while(tpx>=2 && interx(lx[i],hx[tpx])<=interx(lx[i],hx[tpx-1])) tpx--;
            hx[++tpx]=lx[i];
        }
        tpy=0;
        FOR(i,1,n){
            if(tpy && ly[i].k==hy[tpy].k) continue;
            while(tpy>=2 && interx(ly[i],hy[tpy])<=interx(ly[i],hy[tpy-1])) tpy--;
            hy[++tpy]=ly[i];
        }
        tot=0;
        int j=1;
        FOR(i,1,tpx){
            double lft=i==1?-1e18:interx(hx[i],hx[i-1]),rig=i==tpx?1e18:interx(hx[i],hx[i+1]);
            while(j<=tpy){
                double L=j==1?-1e18:interx(hy[j],hy[j-1]),R=j==tpy?1e18:interx(hy[j],hy[j+1]);
                if(L>rig) break;
                if(R>=lft) h[++tot]=merge(hx[i],hy[j]);
                if(R>rig) break;
                j++;
            }
        }
        int ans1=0,ans2=0;
        FOR(i,1,tot){
            double lft=i==1?-1e18:interx(h[i],h[i-1]),rig=i==tot?1e18:interx(h[i],h[i+1]);
            double x=1.0*(l-h[i].b)/h[i].k;
            if(x>=lft && x<=rig){
                ans1=h[i].id1;
                ans2=h[i].id2;
                break;
            }
        }
        printf("%d %d\n",ans1,ans2);
        FOR(i,1,n-1) if(lx[i].id1==ans1) swap(lx[i],lx[i+1]);
        FOR(i,1,n-1) if(ly[i].id1==ans2) swap(ly[i],ly[i+1]);
        n--;
    }
}