RT，在 LOJ 上开了 O3 还有 k=4 中的一部分点不过

#define UP(i, s, e) for(auto i=s; i<e; ++i)
bool check4(int x, int mn, int mx, int dmn){ // mx on first{{{

    static std::vector<
        std::tuple<int, int, int, int>> pts; // x, delta, yl, yr
  // 名为 pts 实际是扫描线的线段
    static std::vector<std::tuple<int, int, int, int>> lines; // x, yl, yr, delta
    static std::multiset<std::pair<int, int>> segs;  //用类珂树维护的扫描线区间
    // x, yl, yr, delta
    pts.clear();
    UP(i, 0, in){
        bool valid = false;
        lines.clear();
        UP(j, 0, 4){
            if(mx-ia[i][j] <= x && ia[i][(1+dmn+j)%4]-mn <= x){
                valid = true;
                int xx = ia[i][(1+(dmn+1)%3+j)%4], 
                    yy = ia[i][(1+(dmn+2)%3+j)%4];
                lines.push_back({
                        xx,
                        yy,
                        std::min(A, yy+x+1),
                        1
                        });
                lines.push_back({
                        std::min(A, xx+x+1),
                        yy,
                        std::min(A, yy+x+1),
                        -1
                        });
            }
        }
        if(!valid) return false;
        segs.clear();
        std::sort(lines.begin(), lines.end());
        int lastx = -1;
        for(auto j:lines){
            if(lastx != -1 && !segs.empty()){
                int lasty = segs.begin()->first;
                for(auto k=segs.begin(); ;){
                    auto add = [&](){

                        pts.push_back({lastx, 1, lasty, k->second});
                        pts.push_back({std::get<0>(j), -1, lasty, k->second});

                    };
                    auto l=k; l++;
                    if(l==segs.end() || l->first > k->second){
                        add();
                        lasty = l->first;
                        if(l == segs.end()) break;
                        k=l;
                    } else {
                        k=l;
                    }
                }
            }
            if(std::get<3>(j) == -1){
                segs.erase(segs.find({std::get<1>(j), std::get<2>(j)}));
            } else {
                segs.insert({std::get<1>(j), std::get<2>(j)});
            }
            lastx = std::get<0>(j);
        }
    }
    std::stable_sort(pts.begin(), pts.end());
    segt::nodcnt = 0;
    segt::Node *rt = segt::build(segt::nnod(), 0, A); // 开 [0, max a_i) 的空线段树，线段树板子略
    for(auto i:pts){
		segt::add(rt, std::get<2>(i), std::get<3>(i), std::get<1>(i));
        if(rt->mx == in) return true;
    }
    return false;
}/*}}}*/
void work4(){
    init(4); // 读入
    int mx=ia[0][0], mn=ia[0][0];
    UP(i, 0, in) UP(j, 0, 4){
        mx = std::max(mx, ia[i][j]);
        mn = std::min(mn, ia[i][j]);
    }
    int l=-1, r=mx-mn+0; // (l, r]
    while(r-l>1){
        //int mid= (r-l) > 100 ? r-(r-l)/4 : (l+r)/2; // 听说这样更快
        int mid = (l+r)/2;
        if(check4(mid, mn, mx, 0) || check4(mid, mn, mx, 1) || check4(mid, mn, mx, 2)){
            r=mid;
        } else l=mid;
    }
    cout << r << '\n';
}