14208: 【原4208】氪金陷阱

题目

题目描述

author: 泰玛什原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4208

Background

小L是一个手游玩家，他在玩游戏的时候经常会忍不住氪金。

Description

为了简单起见，我们将小L的游戏世界简化成一个无限大的棋盘。每天在他打游戏的过程被看作是从位置\((x_1; y_1)\)走到\((x_2; y_2)\)。同时在每个位置，他都可以向上下左右四个方向移动。

在这个棋盘上，有些位置被游戏厂商设计了氪金陷阱，当他走到这个位置，就会忍不住剁手。

对于一个位置\((x; y)\)，若以下至少有一点满足，那么该位置便是一个氪金陷阱：

若\(|x+y| \equiv 0 \quad (\mod 2a)\)，此处会有商店打折活动。
若\(|x-y| \equiv 0 \quad (\mod 2b)\)，此处会有限定皮肤活动。

这个月活动太多，为了让他月底不吃土，你需要告诉他从\((x_1; y_1)\)走到\((x_2; y_2)\)至少会经过多少氪金陷阱。

Input Format

第一行一个整数n，表示数据组数。

接下来n行，每行6个整数\(a,b,x_1,y_1,x_2,y_2\)，含义如上所述。

Output Format

一共n行，每行一个数，表示从\((x_1; y_1)\) 走到\((x_2; y_2)\)，最少会遇到多少个氪金陷阱。

Sample Input

1
2 4 3 -1 3 7

Sample Output

Limits

对于前30%的数据， \(|x_1| = |y_1|\)
对于前60%的数据， \(|x_1|, |y_1|, |x_2|, |y_2| \leq 10^3\)
对于100%的数据， \(2\leq a, b \leq 10^9\) 且 \(|x_1|, |y_1|, |x_2|, |y_2| \leq 10^9\) \(1\leq n \leq10\)，同时数据保证\((x_1; y_1)\)和\((x_2; y_2)\)均不是氪金陷阱。

Hint

一条可能的移动路径是(3;-1)->(3;0)->(3;1)->(3;2)->(4;2)->(4;3)->(4;4)->(4;5)->(4;6)->(4;7)->(3;7)，其中(3;1)和(4;4)是氪金陷阱。

Hint 2

适度氪金益脑，过度氪金伤身

ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "cmath"
using namespace std;

int main() {
    int n;
    cin >> n;

    for (; n > 0; --n) {
        int a, b, x1, y1, x2, y2;
        scanf("%d %d %d %d %d %d", &b, &a, &x1, &y1, &x2, &y2);
        a *= 2, b *= 2;
        int m1 = floor(double(x1 - y1) / a), n1 = floor(double(x1 + y1) / b),
            m2 = floor(double(x2 - y2) / a), n2 = floor(double(x2 + y2) / b);
        if (abs(m1 - m2) > abs(n1 - n2)) {
            printf("%d\n", abs(m1 - m2));
        }
        else {
            printf("%d\n", abs(n1 - n2));
        }
    }

    return 0;
}

q4x3's solution

/**
 * 数学题
 * 横线竖线中较多的那一个
 **/
#include <iostream>
#include <stdio.h>

using namespace std;

int main() {
    int n, a, b, x1, y1, x2, y2, tmp1, tmp2, tmp3, tmp4;
    cin >> n;
    for(int i = 0;i < n;++ i) {
        cin >> a >> b >> x1 >> y1 >> x2 >> y2;
        tmp1 = (x1 - y1) / (2 * b);
        tmp2 = (x2 - y2) / (2 * b);
        tmp3 = (x1 + y1) / (2 * a);
        tmp4 = (x2 + y2) / (2 * a);
        if(x1 - y1 < 0) -- tmp1;
        if(x2 - y2 < 0) -- tmp2;
        if(x1 + y1 < 0) -- tmp3;
        if(x2 + y2 < 0) -- tmp4;
        if(abs(tmp1 - tmp2) > abs(tmp3 - tmp4)) cout << abs(tmp1 - tmp2) << endl;
        else cout <<  abs(tmp3 - tmp4) << endl;
    }
}

skyzh's solution

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    double a, b, x1, y1, x2, y2;
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> a >> b >> x1 >> y1 >> x2 >> y2;

        double resL = floor((x1 + y1) / a / 2.0) - floor((x2 + y2) / a / 2.0);
        double resR = floor((x1 - y1) / b / 2.0) - floor((x2 - y2) / b / 2.0);
        cout << (int)round(max(fabs(resL), fabs(resR))) << endl;
    }
    return 0;
}

victrid's solution

#include <cmath>
#include <iostream>
using namespace std;

int main() {
    long long n, a, b, x1, y1, x2, y2;
    cin >> n;
    while (n--) {
        cin >> a >> b >> x1 >> y1 >> x2 >> y2;
        cout << (long long)max(abs(floor((x1 + y1) / (double)(2 * a)) - floor((x2 + y2) / (double(2 * a)))), abs(floor((x1 - y1) / (double)(2 * b)) - floor((x2 - y2) / (double(2 * b))))) << endl;
    }
    return 0;
}