lightoj1202

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

27 8月 2015

1202 - Bishops

Now you are given the position of the two bishops. You have to find the minimum chess moves to take one to another. With a chess move, a bishop can be moved to a long distance (along the diagonal lines) with just one move.There is an Infinite chessboard. Two bishops are there. (Bishop means the chess piece that moves diagonally).

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains four integers r₁ c₁ r₂ c₂ denoting the positions of the bishops. Each of the integers will be positive and not greater than 10⁹. You can also assume that the positions will be distinct.

Output

For each case, print the case number and the minimum moves required to take one bishop to the other. Print 'impossible' if it's not possible.

Sample Input	Output for Sample Input
31 1 10 101 1 10 111 1 5 3	Case 1: 1Case 2: impossibleCase 3: 2

题目类型：简单数学

算法分析：如果两个点的坐标都不相等且之间的直线的斜率为1或者是-1，则输出1，反之继续判断。判断的思路是做两条过两点，斜率分别为1和-1的直线，判断两直线的交点是否在整数点上

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 1e9 + 7;
const int maxn = 10000 + 66;


int main()
{
//    ifstream cin ("aaa.txt");

    int t,  flag = 1;
    cin >> t;

    while (t--)
    {
        cout << "Case " << flag++ << ": ";

        long long a1, b1, a2, b2;
        cin >> a1 >> b1 >> a2 >> b2;

        if (a2 != a1 && b2 != b1 && (b2 - b1) % (a2 - a1) == 0)
        {
            int temp = (b2 - b1) / (a2 - a1);
            if (temp == 1 || temp == -1)
            {
                cout << "1" << endl;
                continue;
            }
        }

        if (abs (a2 + b2 + a1 - b1) % 2)
            cout << "impossible" << endl;

        else
            cout << "2" << endl;
    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 1e9 + 7;

const int maxn = 10000 + 66;

int main()

{

// ifstream cin ("aaa.txt");

int t, flag = 1;

cin >> t;

while (t--)

{

cout << "Case " << flag++ << ": ";

long long a1, b1, a2, b2;

cin >> a1 >> b1 >> a2 >> b2;

if (a2 != a1 && b2 != b1 && (b2 - b1) % (a2 - a1) == 0)

{

int temp = (b2 - b1) / (a2 - a1);

if (temp == 1 || temp == -1)

{

cout << "1" << endl;

continue;

}

if (abs (a2 + b2 + a1 - b1) % 2)

cout << "impossible" << endl;

else

cout << "2" << endl;

}

return 0;

}

lightoj1198

lightoj1212

一	二	三	四	五	六	日
« 6月
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

超客的水墨烟雨

lightoj1202

Input

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论