最近距离 - 第四届全国中医药院校大学生程序设计竞赛

2020-02-20 本文已影响0人 Void_Caller

问题描述

在平面上有 $n$ 个边平行坐标轴的正方形，编号依次为 $1,2,...,n$ ，每个正方形都占据了若干个格子。第i个正方形的中心位于格子 $(x_i,y_i)$ ，其半径为 $r_i$ ，即它的左下角为格子 $(x_i-r_i,y_i-r_i)$ ，右上角为格子 $(x_i+r_i,y_i+r_i)$ ，共占据 $(2r_i+1)^2$ 个格子。

定义正方形 $i$ 和正方形 $j$ 的距离为：从正方形i占据的格子中选择一个格子 $(x_1,y_1)$ ，从正方形j占据的格子中选择一个格子 $(x_2,y_2)$ ，使得这两个格子的曼哈顿距离 $|x_1-x_2|+|y_1-y_2|$ 最小，此时这两个代表格子之间的曼哈顿距离被视为这两个正方形的距离。

请写一个程序，快速支持 $m$ 次操作，操作有以下两种：

1 i x y r将第 $i$ 个正方形的中心改为 $(x,y)$ ，半径改为 $r$ 。
2 u v询问如果在编号在 $[u,v]$ 之间的所有正方形之中挑选两个编号不同的正方形，那么它们的距离的最小值是多少。

输入

第一行包含一个正整数 $T(1 <= T <= 3)$ ，表示测试数据的组数。

每组测试数据第一行包含两个正整数 $n,m(2 <= n,m <= 100000)$ ，分别表示正方形的数量以及操作的数量。

接下来 $n$ 行，每行三个正整数 $x_i,y_i,r_i(1 <= x_i,y_i,r_i <= 10)$ ，依次描述每个正方形。

接下来 $m$ 行，每行描述一个操作，其中 $1 <= i <= n, 1 <= x,y,r <= 10, 1 <= u<v <= n$ 。

输出

对于每个询问，输出一行一个整数，即距离的最小值。

样例输入

样例输出

3
1
0

解题思路

首先先理解下题意，假如说半径为1的一个正方形，那么就是一个 $3\times3$ 的一个大正方形，半径为2那就是 $5\times5$ 。

题目的要求是让我们在这样的大正方形中任意找一个小正方形，然后求他们的距离： $|x_1-x_2|+|y_1-y_2|$ ，这边的 $x_1,y_1;x_2,y_2$ 分别对应的就是两个小正方形的 $x,y$ ，因此，只要不重叠，他们之间一定会有一定的距离。换言之，就是只要重叠了，那么他们的距离就是0。

我们先把代码的大致框架写好，然后再来分情况讨论。_{（注释已经很清晰了。）}

int main()
{
    int T; // T组测试数据
    scanf("%d",&T);
    int n,m;
    int op;
    int a,b,c,d;
    while (T --)
    {
        scanf("%d %d",&n,&m);
        for (int i = 1;i <= n;i ++)
        {
            scanf("%d %d %d",x + i,y + i,r + i); // 按题意读入n个正方形，x，y，r是三个数组，分别记录每个正方形的x，y，r
        }
        for (int v = 0;v < m;v ++)
        {
            scanf("%d",&op);
            if (op == 1)
            {
                scanf("%d %d %d %d",&a,&b,&c,&d); // 操作1，就是简单的更新正方形
                x[a] = b;
                y[a] = c;
                r[a] = d;
            } else { // 操作2
                scanf("%d %d",&a,&b); // 按题意读入u，v，一个范围
                int miin = -1; // 题目的意思是求编号从u开始到v中最小的两个正方形距离，由于数据给得很小，所以可以直接暴力。
                for (int i = a;i <= b - 1;i ++)
                {
                    for (int j = i + 1;j <= b;j ++)
                    {
                        if (miin == -1) miin = ck(i,j);
                        else miin = min(miin,ck(i,j)); // 找最小，用check函数
                        if (miin == 0) goto ok; // 暴力中，如果发现正方形重叠了，那么一定是最小了，可以直接跳出循环
                    }
                }
                ok:
                printf("%d\n",miin); // 输出答案
            }
        }
    }
    return 0;
}

上述代码把一个大致的框架打好了，现在我们只需要来写check函数就行了，这个函数的任务就是来计算两个正方形之间的距离。

重叠

首先我们先来判断一下两个正方形是否重叠，重叠了那就直接return 0;就行了。

if (cf(a,b)) return 0;

所以我们来先写一下重叠函数。

那么重叠用哪些情况呢，我们可以大致想一下。

三个情况

大致就上图的三种情况。

那么我们可以发现一个普遍的规律：只要一个正方形相邻的两条边在另一个正方形里面，那么他们一定是重叠的。

那代码就好写了啊，((x[b] - r[b] >= x[a] - r[a] && x[b] - r[b] <= x[a] + r[a]) || (x[b] + r[b] >= x[a] - r[a] && x[b] + r[b] <= x[a] + r[a])) && ((y[b] - r[b] >= y[a] - r[a] && y[b] - r[b] <= y[a] + r[a]) || (y[b] + r[b] >= y[a] - r[a] && y[b] + r[b] <= y[a] + r[a]))，这就是那个条件，嗯，看上去挺复杂的，那我们分解一下来看。

先从中间的那个&&号开始分离。那么前面的就是计算x轴的，后面的就是计算y轴的，也就是分别计算相邻的两条边是否符合。

那么我们以x轴为例：(x[b] - r[b] >= x[a] - r[a] && x[b] - r[b] <= x[a] + r[a]) || (x[b] + r[b] >= x[a] - r[a] && x[b] + r[b] <= x[a] + r[a])，还是很复杂对吧，在分解呗。。。

我们再以中间的||来分解这个式子。左边的就是x[b] - r[b] >= x[a] - r[a] && x[b] - r[b] <= x[a] + r[a]，右边的则是x[b] + r[b] >= x[a] - r[a] && x[b] + r[b] <= x[a] + r[a]。很显然，x[b] - r[b]描述的正是 $正方形b$ 所对应的左边的那条边，而x[a] - r[a]和x[a] + r[a]则是 $正方形a$ 的左右两条边。

也就是说，||左边所描述的，便是正方形b的左边得在正方形a的左右两条边之间。那么为什么可以取=呢？因为这些正方形并非传统意义上的那些连续的正方形，他是离散的，由一个个小正方形构成，所以说，相等的时候他们是重叠的。

同样的，||右边所描述的，便是正方形b的右边在正方形a的左右两条边之间的判断。

y轴也是同理。

if (((x[b] - r[b] >= x[a] - r[a] && x[b] - r[b] <= x[a] + r[a]) || (x[b] + r[b] >= x[a] - r[a] && x[b] + r[b] <= x[a] + r[a])) && ((y[b] - r[b] >= y[a] - r[a] && y[b] - r[b] <= y[a] + r[a]) || (y[b] + r[b] >= y[a] - r[a] && y[b] + r[b] <= y[a] + r[a])))
{
    return 1; // 如果正确就直接返回1
}

但是这样还存在一个问题，这样的描述必须符合一个条件正方形b必须比正方形a小，也就是上图中绿色的正方形。

那我们在判断一次不就好了吗。。。

因此我们交换a，b。

a = a ^ b;
b = a ^ b;
a = a ^ b;

之后我们在判断一次就完成了，cf函数完整代码如下

//判断重叠
int cf(int a, int b)
{
    if (((x[b] - r[b] >= x[a] - r[a] && x[b] - r[b] <= x[a] + r[a]) || (x[b] + r[b] >= x[a] - r[a] && x[b] + r[b] <= x[a] + r[a])) && ((y[b] - r[b] >= y[a] - r[a] && y[b] - r[b] <= y[a] + r[a]) || (y[b] + r[b] >= y[a] - r[a] && y[b] + r[b] <= y[a] + r[a])))
    {
        return 1;
    }
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    if (((x[b] - r[b] >= x[a] - r[a] && x[b] - r[b] <= x[a] + r[a]) || (x[b] + r[b] >= x[a] - r[a] && x[b] + r[b] <= x[a] + r[a])) && ((y[b] - r[b] >= y[a] - r[a] && y[b] - r[b] <= y[a] + r[a]) || (y[b] + r[b] >= y[a] - r[a] && y[b] + r[b] <= y[a] + r[a])))
    {
        return 1;
    }
    return 0;
}

计算两正方形距离

我们首先观察他给出的距离公式： $|x_1-x_2|+|y_1-y_2|$ ，很显然，只要让 $|x_1 - x_2|$ 和 $|y_1 - y_2|\to0$ 就行了。

~~当然可以分类讨论，但是比赛的时候就因为没有考虑全（有超级多情况，不值得去讨论），然后wa了很多回。~~

看了下数据量，挺小的，那暴力找最小吧。

int mix = -1;
//直接双指针暴力x，找最小
for (int i = x[a] - r[a];i <= x[a] + r[a];i ++) // 从a正方形的左边跑到右边
{
    for (int j = x[b] - r[b];j <= x[b] + r[b];j ++) // 从b正方形的左边跑到右边
    {
        if (mix == -1) mix = abs(i - j);
        else mix = min(mix,abs(i - j)); // 按照题意找min_x
        if (mix == 0) goto x_done; // 如果找到最小=0了（同一行），那直接跳出
    }
}
x_done:

y轴同理，不说了，下面直接完整的这个函数的代码。

int ck(int a, int b)
{
    if (cf(a,b))
    {
        return 0;
    }
    int mix = -1;
    //直接暴力x
    for (int i = x[a] - r[a];i <= x[a] + r[a];i ++)
    {
        for (int j = x[b] - r[b];j <= x[b] + r[b];j ++)
        {
            if (mix == -1) mix = abs(i - j);
            else mix = min(mix,abs(i - j));
            if (mix == 0) goto x_done;
        }
    }
    x_done:
    //暴力y
    int miy = -1;
    for (int i = y[a] - r[a];i <= y[a] + r[a];i ++)
    {
        for (int j = y[b] - r[b];j <= y[b] + r[b];j ++)
        {
            if (miy == -1) miy = abs(i - j);
            else miy = min(miy,abs(i - j));
            if (miy == 0) goto y_done;
        }
    }
    y_done:
    return mix + miy;
}

代码

老规矩，放ac代码。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <list>
#include <set>
#include <utility> // pair
#include <map>
#include <iostream>
#include <sstream>
#include <algorithm> // sort
#include <string>
#include <stack>
#include <queue>
#include <fstream>

using namespace std;

#define ll long long
#define uchar unsigned char
#define ushort unsigned short
#define uint unsigned int
#define ulong unsigned long
#define ull unsigned long long

#define pi acos(-1)

#define mx(a,b) (a) > (b) ? (a) : (b)
#define mn(a,b) (a) < (b) ? (a) : (b)
#define mem(a,b) memset(a,b,sizeof(a))
#define fre(a) freopen(a,"r",stdin)

#define itn int
#define nit int
#define inr int
#define mian main
#define ednl endl
#define fro for
#define fir for
#define reutrn return
#define retunr return

int r[100010];
int x[100010];
int y[100010];

//判断重叠
int cf(int a, int b)
{
    if (((x[b] - r[b] >= x[a] - r[a] && x[b] - r[b] <= x[a] + r[a]) || (x[b] + r[b] >= x[a] - r[a] && x[b] + r[b] <= x[a] + r[a])) && ((y[b] - r[b] >= y[a] - r[a] && y[b] - r[b] <= y[a] + r[a]) || (y[b] + r[b] >= y[a] - r[a] && y[b] + r[b] <= y[a] + r[a])))
    {
        return 1;
    }
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    if (((x[b] - r[b] >= x[a] - r[a] && x[b] - r[b] <= x[a] + r[a]) || (x[b] + r[b] >= x[a] - r[a] && x[b] + r[b] <= x[a] + r[a])) && ((y[b] - r[b] >= y[a] - r[a] && y[b] - r[b] <= y[a] + r[a]) || (y[b] + r[b] >= y[a] - r[a] && y[b] + r[b] <= y[a] + r[a])))
    {
        return 1;
    }
    return 0;
}

// 计算
int ck(int a, int b)
{
    if (cf(a,b))
    {
        return 0;
    }
    int mix = -1;
    //直接暴力x
    for (int i = x[a] - r[a];i <= x[a] + r[a];i ++)
    {
        for (int j = x[b] - r[b];j <= x[b] + r[b];j ++)
        {
            if (mix == -1) mix = abs(i - j);
            else mix = min(mix,abs(i - j));
            if (mix == 0) goto x_done;
        }
    }
    x_done:
    //暴力y
    int miy = -1;
    for (int i = y[a] - r[a];i <= y[a] + r[a];i ++)
    {
        for (int j = y[b] - r[b];j <= y[b] + r[b];j ++)
        {
            if (miy == -1) miy = abs(i - j);
            else miy = min(miy,abs(i - j));
            if (miy == 0) goto y_done;
        }
    }
    y_done:
    return mix + miy;
}

int main()
{
    int T;
    scanf("%d",&T);
    int n,m;
    int op;
    int a,b,c,d;
    while (T --)
    {
        scanf("%d %d",&n,&m);
        for (int i = 1;i <= n;i ++)
        {
            scanf("%d %d %d",x + i,y + i,r + i);
        }
        for (int v = 0;v < m;v ++)
        {
            scanf("%d",&op);
            if (op == 1)
            {
                scanf("%d %d %d %d",&a,&b,&c,&d);
                x[a] = b;
                y[a] = c;
                r[a] = d;
            } else {
                scanf("%d %d",&a,&b);
                int miin = -1;
                for (int i = a;i <= b - 1;i ++)
                {
                    for (int j = i + 1;j <= b;j ++)
                    {
                        if (miin == -1) miin = ck(i,j);
                        else miin = min(miin,ck(i,j));
                        if (miin == 0) goto ok;
                    }
                }
                ok:
                printf("%d\n",miin);
            }
        }
    }
    return 0;
}