Squares

Created by LXC on Thu Jul 6 14:29:50 2023

https://codeforces.com/problemset/problem/123/B

ranting: 1800

tag: math

problem

给出一个两个坐标点(x1,y1)和(x2,y2)。

对于坐标点(x,y)每次移动可以移动到(x+1,y),(x-1,y),(x,y+1),(x,y-1)四个位置中的一个。

问从(x1,y1)移动到(x2,y2)需要最少经过多少个坏点。

若当前坐标为(x,y)，当以下条件满足至少一个则(x,y)为坏点。

• x+y是2a的倍数
• x-y是2b的倍数

solution

很有意思的一道题

对于x+y是2a倍数的点形成了无数条相距为2a的平行线。

对于x-y是2a倍数的点形成了无数条相距为2b的平行线。

且这两类平行线是垂直的。在二维平面上形成了一张网格图。每个网格的大小是2a*2b。

现在只需要找到两个点之间每一类平行线经过了多少条就行了。我们只需要将最多的一类平行线作为答案就行，因为我们可以从它们的交点经过。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

ll up(ll u, ll d) {
    if (u >= 0)
        return (u + d - 1) / d * d;
    return u / d * d;
}

ll dw(ll u, ll d) {
    if (u >= 0)
        return u / d * d;
    return (u - d + 1) / d * d;
}

void sol() {
    ll a, b, x1, y1, x2, y2;
    cin >> a >> b >> x1 >> y1 >> x2 >> y2;
    ll p1 = x1 + y1, p2 = x2 + y2;
    if (p1 > p2)
        swap(p1, p2);
    ll q1 = x1 - y1, q2 = x2 - y2;
    if (q1 > q2)
        swap(q1, q2);
    ll ans1 = (dw(p2, 2 * a) - up(p1, 2 * a)) / (2 * a) + 1;
    ll ans2 = (dw(q2, 2 * b) - up(q1, 2 * b)) / (2 * b) + 1;
    cout << max(ans1, ans2) << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}