QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#596523#9168. Square LocatorHans#TL 0ms3956kbC++232.9kb2024-09-28 15:57:342024-09-28 15:57:34

Judging History

你现在查看的是最新测评结果

  • [2024-09-28 15:57:34]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3956kb
  • [2024-09-28 15:57:34]
  • 提交

answer

#include <cmath>
#include <iostream>

using namespace std;

struct coord {
  long long int x;
  long long int y;
};

#define _d(x, y) (pow((x), 2) + pow((y), 2))

struct coord a;
long long int da, db, dc, dd;
long long int bs, bl;

void find(long long int d, long long int low, long long int high) {
  // Binary search high
  long long int h = high, l = low;
  long long int mh = high;

  long long int sumD = _d(mh, l);
  long long int sumN = _d(mh+1, l);

  while (!(sumD <= d && sumN > d)) {
    if (sumD <= d) {
      l = mh;
    } else {
      h = mh;
    }
    mh = (l + h + 1)/2;
    sumD = _d(mh, low);
    sumN = _d(mh+1, low);
  }

  if (_d(low, mh) == d) {
    bs = low;
    bl = mh;
    return;
  }
  // printf("mh is: %d\n", mh);

  // Binary search low
  h = mh, l = low;
  long long int ml = low;
  sumD = _d(ml, mh);
  sumN = _d(ml-1, mh);

  while (!(sumD >= d && sumN < d)) {
    if (sumD < d) {
      l = ml;
    } else {
      h = ml;
    }
    ml = (l+h+1)/2;
    sumD = _d(mh, ml);
    sumN = _d(mh, ml-1);
  }

  // printf("%d %d\n", ml, mh);
  if (_d(ml, mh) == d) {
    bs = ml;
    bl = mh;
    return;
  }
  
  
  find(d, ml, mh);
}

bool test(long long int x, long long int y) {
  struct coord b, c, d;
  b.x = a.x + x;
  b.y = a.y + y;

  c.x = b.x - y;
  c.y = b.y + x;

  d.x = c.x - x;
  d.y = c.y - y;

  // printf("%d %d, %d %d, %d %d\n", b.x, b.y, c.x, c.y, d.x, d.y);
  long long int _db, _dc, _dd;
  _db = pow(b.x,2) + pow(b.y, 2);
  _dc = pow(c.x,2) + pow(c.y, 2);
  _dd = pow(d.x,2) + pow(d.y, 2);

  // printf("%d %d %d\n", _db, _dc, _dd);

  if (
    _db == db &&
    _dc == dc &&
    _dd == dd
  ) {
    printf("%lld %lld %lld %lld %lld %lld %lld", a.y, b.x, b.y, c.x, c.y, d.x, d.y);
    return true;
  }
  return false;
}


int main() {
  cin >> da >> db >> dc >> dd;

  a = {0ll, (int)sqrt(da)};

  // while (true) {
  //   // long long int x, y;
  //   // cin >> x >> y;
  //   // test(a, x, y);
  //
  //   // long long int x;
  //   // cin >> x;
  //   // find(x, 0, (int)sqrt(x) + 1);
  //   // printf("Ans: %d %d\n", sa, sb);
  // }

  find(db, 0, (long long int)sqrt(db)+1);

  while (true) {
    long long int rotX = bs - a.x;
    long long int rotY = bl - a.y;

    // cout << rotX << rotY;

#define check if (found) return 0;
    bool found = false;
    found = test(rotX, rotY); check
    found = test(rotX, -rotY); check
    found = test(-rotX, -rotY); check
    found = test(-rotX, rotY); check

    found = test(rotY, rotX); check
    found = test(rotY, -rotX); check
    found = test(-rotY, -rotX); check
    found = test(-rotY, rotX); check
    ;
    if (!found) {
      bl--;
      
      bs = sqrt(db - pow(bl, 2)) + 1;

      if (bs > bl) {
        return 0;
      }

      find(db, bs, bl-1);
    }
  }
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3908kb

input:

36 5 10 41

output:

6 -1 2 3 1 4 5

result:

ok Answer is correct

Test #2:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

1 1 1 1

output:

1 0 1 0 1 0 1

result:

ok Answer is correct

Test #3:

score: 0
Accepted
time: 0ms
memory: 3956kb

input:

1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000

output:

1000000000 0 1000000000 0 1000000000 0 1000000000

result:

ok Answer is correct

Test #4:

score: 0
Accepted
time: 0ms
memory: 3956kb

input:

4 10 8 2

output:

2 -1 3 -2 2 -1 1

result:

ok Answer is correct

Test #5:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

4 50 104 58

output:

2 5 5 2 10 -3 7

result:

ok Answer is correct

Test #6:

score: -100
Time Limit Exceeded

input:

9 16 65 58

output:


result: