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

问题描述

在平面上有 $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;
}

最后编辑于：2020.02.20 18:05:17

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 217,907评论 6赞 506
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,987评论 3赞 395
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 164,298评论 0赞 354
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,586评论 1赞 293
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,633评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,488评论 1赞 302
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,275评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,176评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,619评论 1赞 314
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,819评论 3赞 336
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,932评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,655评论 5赞 346
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,265评论 3赞 329
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,871评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,994评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,095评论 3赞 370
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,884评论 2赞 354