#P12676. [集训队互测2025day10]计算几何

    ID: 11862 传统题 4000ms 1024MiB 尝试: 3 已通过: 2 难度: 10 上传者: 标签>CF2900省选/NOI-最近点对扫描线有序集合滑动窗口哈希表链表查询排序树状数组

[集训队互测2025day10]计算几何

题目描述

给定一个包含 nn 个点的序列,第 ii 个点的坐标为 (ai,bi)(a_i, b_i) 。

共有 qq 次询问,每次询问一个区间 [l,r][l, r] ,你需要求出下面式子的值。

$$\min_{i=l}^r \min_{j=i+1}^r (\|a_i - a_j\| + \|b_i - b_j\|)$$

保证序列中点的坐标和询问区间在指定范围内用指定方式随机生成。

输入格式

第一行输入两个正整数 n,qn, q 。

接下来 nn 行,每行输入两个整数 ai,bia_i, b_i ,表示第 ii 个点的坐标为 (ai,bi)(a_i, b_i) 。

接下来 qq 行,每行输入两个正整数 l,rl, r ,表示询问区间 [l,r][l, r] 。

输出格式

输出 qq 行,每行包含一个非负整数,表示答案。

样例一输入

4 5
1 1
2 2
1 2
2 1
1 4
1 3
1 2
2 3
3 4

样例一输出

1
1
2
1
2

样例二

见下发文件下的 geo2.in 与 geo2.ans 。

该样例约束与测试点 22 一致。

样例三

见下发文件下的 geo3.in 与 geo3.ans 。

该样例约束与测试点 1818 一致。

下发文件

本题下发的文件除三个样例外还有 rand.cpp 。

rand.cpp 是一个数据生成器,与生成评测用例的数据生成器仅有随机种子不同。

输入 n,q,A,Bn, q, A, B 后数据生成器才可生成整个数据,数据输出到 geo.in ,其中 A,BA, B 分别表示 ∥ai∥\|a_i\| 与 ∥bi∥\|b_i\| 的上界。

数据范围

对于所有测试点, 2≤n≤1062 \le n \le 10^6 , 1≤q≤1061 \le q \le 10^6 , ∥ai∥,∥bi∥≤109\|a_i\|, \|b_i\| \le 10^9 , 1≤l<r≤n1 \le l < r \le n ,保证 ai,bi,l,ra_i, b_i, l, r 在指定范围内用指定方式随机生成。

测试点表格

测试点编号$n \le$$q \le$
$1 \sim 2$$2 \times 10^3$$2 \times 10^3$
$3 \sim 8$$2 \times 10^4$$2 \times 10^4$
$9 \sim 14$$2 \times 10^5$$2 \times 10^5$
$15 \sim 16$$2 \times 10^3$$10^6$
$17 \sim 19$$10^6$$10$
$20 \sim 25$$10^6$$10^6$

对于每一档部分分,设其测试点编号范围为 l∼rl \sim r ,则测试点 l+1∼r−1l+1 \sim r-1 满足 ∥ai∥,∥bi∥≤106\|a_i\|, \|b_i\| \le 10^6 ,测试点 ⌊l+r2⌋+1∼r\lfloor \frac{l+r}{2} \rfloor + 1 \sim r 满足 bi=0b_i = 0 。

提示

本题输入输出规模较大,请使用较为快速的输入输出方式。


#include <iostream>
#include <random>
using namespace std;
mt19937_64 Rand('C'^'h'^'e'^'r'^'i'^'s'^'h'^'e'^'d');
#define rand Rand
int main() {
    freopen("geo.in", "w", stdout);
    ios::sync_with_stdio(false);
    int n, q, A, B;
    cin >> n >> q >> A >> B;
    cout << n << " " << q << '\n';

    for (int i = 1; i <= n; i++) {
        cout << int(rand() % ((A << 1) + 1)) - A << " "
             << int(rand() % ((B << 1) + 1)) - B << '\n';
    }

    for (int i = 1; i <= q; i++) {
        int L = rand() % (n - 1) + 2, l = rand() % (n - L + 1) + 1;
        cout << l << " " << l + L - 1 << '\n';
    }

    return 0;
}


#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n,q,a[1001001],b[1001001],ans[1001001];
int ls[1001001],rs[1001001];
void solve(vector<int>&u,vector<int>&v){
    if(v.size()==0||u.size()<2)return ;
    // cout<<u.size()<<"~~~"<<v.size()<<"\n";
    // for (auto i:u)cout<<i<<" "<<a[i]<<" "<<b[i],cout<<"\n";
    // for (auto i:v)cout<<ls[i]<<"&"<<rs[i],cout<<"\n";
    int n=u.size();
    int mn=1e18,l,r;
    for (int i=0;i<n;i++)
    for (int j=i+1;j<=i+10&&j<n;j++){
        int tmp=abs(a[u[i]]-a[u[j]])+abs(b[u[i]]-b[u[j]]);
        if(tmp<mn)mn=tmp,l=u[i],r=u[j];
    }
    if(l>r)swap(l,r);
    // cout<<l<<"$$"<<r<<"\n";
    vector<int>ul,ur,vl,vr;
    for (auto i:u){
        if(i<r)ul.push_back(i);
        if(l<i)ur.push_back(i);
    }
    for (auto i:v){
        if(ls[i]<=l&&r<=rs[i])ans[i]=mn;
        else {
            if(rs[i]<r)vl.push_back(i);
            else vr.push_back(i);
        }
    }
    solve(ul,vl);solve(ur,vr);
}
bool cmp(int x,int y){
    return a[x]<a[y]||(a[x]==a[y]&&b[x]<b[y]);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    vector<int>u,v;
    for (int i=1;i<=n;i++)
    cin>>a[i]>>b[i],u.push_back(i);
    sort(u.begin(),u.end(),cmp);
    for (int i=1;i<=q;i++)
    v.push_back(i),cin>>ls[i]>>rs[i],ans[i]=0;
    solve(u,v);
    for (int i=1;i<=q;i++)
    cout<<ans[i]<<"\n";
}