前排提示: BLY倾情力作

题目链接: Peekaboo

Peekaboo

Description:
Tension is in the air! You are playing a game Peekaboo with Kblack and CSL. All of you are in a 2D grid. You are at point (0, 0)(0,0). Kblack and CSL has hidden themselves at some lattice point (xx-coordinate and yy-coordinate are both integers) out of your sight, but you have the psycho connection that tells you the distance between you and Kblack is aa, the distance between you and CSL is bb and the distance between Kblack and CSL is cc. You now want to know all the possible positions of Kblack and CSL.

InputFile
The first line is an integer TT (1≤T≤20), which is the number of cases.

The next TT lines each have three space-separated integers a, b, ca,b,c (1≤a,b,c≤1e9), respectively denoting the distance in the problem statement.

OutputFile
For each case, you should output firstly in a line, an integer nn, which is the number of possible positions.

For the next nn lines, each line contains four space-separated integers x1, y1, x2, y2
which are the Kblack's position and CSL's position. In particular, the possible positions should follow the lexicographical order. The data guarantees that ∑n≤1e5

样例输入
2
1 1 1
3 4 5
样例输出
0
8
-3 0 0 -4
-3 0 0 4
0 -3 -4 0
0 -3 4 0
0 3 -4 0
0 3 4 0
3 0 0 -4
3 0 0 4

Problem solving:
这道题的意思就是你在原点，即（0，0），现在有两个人，其中一个跟你的距离为a，另外一个人跟你的距离为b，并且你知道他们两个人之间的距离是c。现在还知道这两个人的坐标都是整数。问你总共有多少种满足情况的坐标并输出。
其实这就很容易想到，先找到那两个人的坐标，然后判断他俩的距离是不是跟给定的是相等的。现在相当于我们知道，所要求的两个点到原点的距离并且他们的坐标是整数。也就可以转换成这类问题：求以原点为圆心，且半径确定的圆在坐标轴上能经过的整数坐标。这也就是我在最开始放的链接。为了防止你在翻上去，我在在这里放一次：圆上整点个数及坐标求解方法-boctorio.
所以这道题也就很显然了，我们分别求出来半径为a，b的圆心为原点的圆上的整数坐标，然后两个for循环判断距离是否为c并输出。剩下的就是一些细节的处理了。具体看代码

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll       n, a, b, c;
#define pll    pair<ll, ll>
ll       d[4][2] = { 1, 1, 1, -1, -1, 1, -1, -1 };
set<pll> se[2];
struct node
{
    ll x1, y1, x2, y2;
};
vector<node> V;
void div(ll r, ll exp, ll flag)
{
    for (ll i = 1; i * i < r; i++)
    {
        ll x = (ll) sqrt(r - i * i);
        if (x * x + i * i == r && x != i)
        {
            ll a = x * x - i * i, b = 2 * x * i;
            for (int j = 0; j < 4; j++)
                se[flag].insert({ d[j][0] * a * exp, d[j][1] * b * exp });
            for (int j = 0; j < 4; j++)
                se[flag].insert({ d[j][0] * b * exp, d[j][1] * a * exp });
        }
    }
}
void lo(ll r, ll flag)
{
    se[flag].clear();
    se[flag].insert({ r, 0ll });
    se[flag].insert({ -r, 0ll });
    se[flag].insert({ 0ll, r });
    se[flag].insert({ 0ll, -r });
    div(r, 1, flag);
    for (ll i = 2; i * i <= r; i++)
    {
        if (r % i == 0)
        {
            div(i, r / i, flag);
            div(r / i, i, flag);
        }
    }
}
void solve()
{
    cin >> n;
    while (n--)
    {
        V.clear();
        ll ans = 0;
        cin >> a >> b >> c;
        lo(a, 0); lo(b, 1);
        for (set<pll>::iterator it = se[0].begin(); it != se[0].end(); it++)
        {
            for (set<pll>::iterator its = se[1].begin(); its != se[1].end(); its++)
            {
                ll x1 = it->first, y1 = it->second, x2 = its->first, y2 = its->second;
                if (sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) == c)
                    ans++, V.push_back({ x1, y1, x2, y2 });
            }
        }
        cout << ans << endl;
        for (int i = 0; i < V.size(); i++)
        {
            cout << V[i].x1 << " " << V[i].y1 << " " << V[i].x2 << " " << V[i].y2 << endl;
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

这道题卡输入，如果不关同步流会TLE

赏