传送门：点击打开链接
题意：一个二维网状格点，先给一个n，然后有n个坐标，表示最开始n个人的坐标，然后给一个m，然后有m个坐标，现在要从m个坐标中选出一个坐标，使得这个坐标到n个坐标的最大距离最小输出最大距离最小是多少，以及最后选出的是m个点中的哪一个， n,m<=1e5,坐标有x和y，均<=1e9
思路：这题还真一下子转不过弯来了- -
首先，很明显答案应该是min{|N[i].x-M[j].x|+|N[i].y-M[j].y|},1<=i<=n,1<=j<=m
问题是，我们如何能快速求出，对于点(M[j].x,M[j].y)，距离它最远的距离是多少
其实我们能够发现，|N[i].x-M[j].x|+|N[i].y-M[j].y|有4种去绝对值的方式。
然后我们能发现，加了绝对值是4种去绝对值方式中最大的。
所以我们直接维护4种取了绝对值的最大值，然后对于某次查询，直接取最大的不就行了- -
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;const int MX = 1e5 + 5;
const int mod = 1e9 + 7;
const LL INF = 0x3f3f3f3f3f3f3f3f;int main() {//FIN;while(~scanf("%*d%*d")) {int n, m;scanf("%d", &n);LL Max[4], x, y;memset(Max, -INF, sizeof(Max));for(int i = 1; i <= n; i++) {scanf("%I64d%I64d", &x, &y);Max[0] = max(Max[0], x + y);Max[1] = max(Max[1], x - y);Max[2] = max(Max[2], -x + y);Max[3] = max(Max[3], -x - y);}scanf("%d", &m);LL ans = INF; int id = 0;for(int i = 1; i <= m; i++) {scanf("%I64d%I64d", &x, &y);LL t = -INF;t = max(t, Max[0] - x - y);t = max(t, Max[1] - x + y);t = max(t, Max[2] + x - y);t = max(t, Max[3] + x + y);if(t < ans) ans = t, id = i;}printf("%I64d\n%d\n", ans, id);}return 0;
}