题解 P2694 【接金币】

Solution

观察到 $1\le n\le 50$ 和 $1\le G\le 5$，就可以知道我们能使用 $\mathcal{O(g.n^2)}$ 的方法切掉这道题。 先给出一个结论：
关于每一个 $x_i,x_j,y_i,y_j(1\le i,j\le n)$，只要 $|x_i-x_j| > |y_i-y_j|$，那么这一个金币就不能被接到。
用样例的第一组数据画个图感性理解一下：

这个样例中 B 落到 x 轴上的时间为 $T_B=|y_b| = 1$，A 落到 x 轴上的时间为 $T_A=|y_a| = 4$， C 落到 x 轴上的时间为 $T_c=|y_c| = 3$，关于任意的这三个点，移动时间的变化量 $\Delta t_1 = |\Delta |x||$，下落时间的变化量 $\Delta t_2 = |\Delta |y||$，当 $\Delta t_1 > \Delta t_2$ 的时候显然就不行了。但是注意 FJ 刚刚开始的时候是在 $(0,0)$ 的，这个不能忘。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 59;

int t,n;

struct node {
    int x,y;
}a[N];

bool cmp(const node &u,const node &v) {
    return u.y <= v.y;
}

void solve() {
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        scanf("%d %d",&a[i].x,&a[i].y);
    }
    for(int i = 0;i < n;i++) {
        for(int j = i + 1;j <= n;j++) {
            if(abs(a[i].x - a[j].x) > abs(a[i].y - a[j].y)) {
                puts("Notabletocatch");
                return;
            }
        }
    }
    puts("Abletocatch");
}

int main() {
    scanf("%d",&t);
    while(t--) solve();
    return 0;
}