【袁】ABC289F数学题+简单动脑筋+dfs回溯

一道简单的数学题

题意：给一组起点和终点以及一个长方形，每次可以在长方形内选一个点（整点），将目前所在的点对称过去，求是否能在 1e6 次内到达终点，如果能，输出每次在长方形内选择的点。

考虑到每次对称后，坐标的奇偶性不变，所以当起点和终点的坐标奇偶性不同时，输出no。

必胜策略如下：

1. 从终点开始（回溯），每次将已有的一个小长方形（包括边长为 0 的点）经过题中长方形对称，对称后为一个更大的长方形（边长翻倍）。

2. 若起点在该长方形内，则输出每次对称的点即可。

注意：事实上，新推出来的大长方形内可行的点只有于原来点奇偶性相同的点，而并不是大长方形内的全部点，若一开始没有判断奇偶性，则上述策略不成立。

#include <bits/stdc++.h>
using namespace std;

int sx, sy, tx, ty, a, b, c, d;

struct note
{
    int a1, a2;
};

note dfs(int st, int a1, int a2, int b1, int b2)
{
    if (st > 1e6)
    {
        cout << "No" << endl;
        exit(0);
    }
    if (a1 <= sx && sx <= a2 && b1 <= sy && sy <= b2)
    {
        cout << "Yes" << endl;
        return {sx, sy};
    }
    note kly = dfs(st + 1, a * 2 - a2, b * 2 - a1, c * 2 - b2, d * 2 - b1);
    int x = kly.a1, y = kly.a2;
    cout << (max(a1, a * 2 - x) + x) / 2 << " " << (max(b1, c * 2 - y) + y) / 2 << endl;
    return {max(a1, a * 2 - x), max(b1, c * 2 - y)};
}

int main()
{
    cin >> sx >> sy;
    cin >> tx >> ty;
    cin >> a >> b >> c >> d;
    if (abs(sx - tx) % 2 == 1 || abs(sy - ty) % 2 == 1)
    {
        cout << "No" << endl;
        return 0;
    }
    dfs(0, tx, tx, ty, ty);
    return 0;
}