The Preliminary Contest for ICPC Asia Shanghai 2019 K. 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

VirMach 便宜 VPS

QNews

QNews