模拟赛题讲解[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;
}