本文主要是介绍HDU 5762 Teacher Bo （特判后暴力），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5762
题意：输入第一行t个测试数据，第二行n个点和点最大坐标m，后n行n个点的坐标。
意思就是给出n个点，问这n个点中有没有两个点的距离和另外两个点的曼哈顿距离相同，注意这两组点可以有一个点是相同的。有的话YES，没有的话NO。
首先可以知道题目中最大的曼哈顿距离是2*m，又因为坐标都是整数，所以最多也就有2*m种距离。再考虑n个点，这n各点可以形成（n - 1） + （n - 2） + ······ + 2 + 1个距离，即（n - 1） * n / 2个，根据鸽笼原理，如果（n - 1） * n / 2 大于2*m，那么一定存在两个距离是相同的。有了这个特判就能够让暴力变得可行。如果没满足上面的条件，那么暴力就好啦。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int a[201000], x[101000], y[101000];
int main() {int t;while(~scanf("%d", &t)) {while(t--) {int n, m;scanf("%d %d", &n, &m);int i, j;for(i = 0; i < n; i++) {scanf("%d %d", x + i, y + i);}int flag = 0;if(n * (n - 1) / 2 > 2 * m) flag = 1; // 鸽笼原理 else {memset(a, 0, sizeof(a));for(i = 0; i < n; i++) {for(j = i + 1; j < n; j++) {if(a[abs(x[i] - x[j]) + abs(y[i] - y[j])] != 0) {flag = 1;break;}else a[abs(x[i] - x[j]) + abs(y[i] - y[j])] = 1;}if(flag) break;}}puts(flag?"YES":"NO");}}return 0;
}这篇关于HDU 5762 Teacher Bo （特判后暴力）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
