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:

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;
}