模拟赛题讲解[12]

来自 yukuai26 2022-08-06 noi.ac #2756

题目描述：

曾经有一个 oj 叫做 bzoj, 里面有一题 bzoj1002 叫狼抓兔子

由于 1002 过于有名且显眼，很多人 A 掉了他，每 A 一次兔子就会少一只，兔子死亡惨重，救救兔子!

兔子为了反击策划了一次行动。

刚开始狼在二维平面上的 $(0,0)$ ，他希望走到 $(10^7,0)$，而有 n 只兔子分为处于位置 $(x_{i},y_{i})$。

当狼与某只兔子的欧几里得距离$\leq p$ 时（$p$可以视为一个无限接近于 $0$ 的正实数, 事实上可以理解为狼和兔子非常非常接近)，兔子就会干扰狼，这样狼会被干扰 $t$ 秒，

随后这只兔子完全任务就会离开。

兔子的目标是使得狼受到尽可能被更多的兔子干扰。

已知狼和兔子运动速度都为 1m/s。另外狼和兔子都知道所有动物的实时位置和实时速度方向。

现在围观的 yukuai26 想知道，假如兔子和狼都绝对聪明，狼会受到多少次兔子的干扰

输入格式：

第一行两个非负整数 $n,t$ ，表示兔子的个数和每次眩晕的时间。

接下来 $n$ 行每行两个整数 $x_{i},y_{i}$ ，表示每只兔子的位置

输出格式：

一个正整数表示答案

输入1：

3 1
1 1
1 2
1000000000 0

输出1：

2

样例解释：

第一只兔子选择去 $(1,0)$ 处等狼，假如狼往右走就会经过 $(1,0)$ ， 假如往上下走，那么兔子可以跟着一起上下移动, 时刻保持在狼右边。

所以狼必定被第一只兔子干扰。第一只兔子干扰狼 $1$ 秒，这 $1$ 秒时间可以让第二只兔子跑过来干扰。

但第三只兔子太远了，所以不可能干扰到狼。

数据规模与约定：

对于前 $20$% 的数据，$n=1$

对于前 $40$% 的数据，$t=0$

对于另 $30$% 的数据，$x_{i}\ge 10^7$

对于 $100$% 的数据，$1 \le n \le 5\times 10^5,~-10^9 \leq x_{i},y_{i} \leq 10^9,t \le 10^3$

题解：

一个很神奇的结论是，这些🐰有的去拦截🐺，不如直接在终点等着

然后就直接把所有🐰按距终点的距离排个序算算就好了

时间复杂度 $O(n\log n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(5e5+15)
#define pf(x) ((x)*(x))
struct node{int x,y;} a[N];
int n,t,c=1e7;
int dis(node k){return pf(k.x-10000000)+pf(k.y);}
bool cmp(node x,node y){return dis(x)<dis(y);}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> t;
    for(int i=1; i<=n; i++)
        cin >> a[i].x >> a[i].y;
    sort(a+1,a+1+n,cmp);
    for(int i=1; i<=n; i++)
    {
        if(c*c>=dis(a[i])) c+=t;
        else return cout << i-1,0;
    }
    cout << n << '\n';
    return 0;
}