QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#137509#2350. Integer CowRd_rainydays#WA 482ms3776kbC++202.1kb2023-08-10 13:37:142023-08-10 13:37:17

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-10 13:37:17]
  • 评测
  • 测评结果:WA
  • 用时:482ms
  • 内存:3776kb
  • [2023-08-10 13:37:14]
  • 提交

answer

#include <bits/stdc++.h>

#define sqr(x) ((x) * (x))
using ll = __int128;
struct Point {
  double x, y;
  Point(double x = 0, double y = 0) : x(x), y(y) { }
};
Point operator + (const Point& a, const Point& b) {
  return Point(a.x + b.x, a.y + b.y);
}
Point operator - (const Point& a, const Point& b) {
  return Point(a.x - b.x, a.y - b.y);
}
double dist(const Point& a, const Point& b) {
  return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}
ll SQRT(ll x) {
  // double t = sqrt(x);
  // if (fabs(t - ceil(t)) < 1e-6) return (ll)ceil(t);
  // if (fabs(t - floor(t)) < 1e-6) return (ll)floor(t);
  // return (ll)floor(t);

  ll lb = 0, ub = 1e18, ans = 0;
  while (lb <= ub) {
    ll mid = (lb + ub) / 2;
    if (mid * mid <= x) ans = mid, ub = mid - 1;
    else lb = mid + 1;
  }

  return ans;
}

ll read() {
  long long x;
  scanf("%lld", &x);
  return x;
}

 
void solve() {
  ll cx = read(), cy = read(), r = read(), px = read(), py = read();

  Point c, p;
  c.x = cx, c.y = cy;
  p.x = px, p.y = py;

  if (sqr(cx - px) + sqr(cy - py) <= sqr(r)) {
    printf("0\n%lld %lld\n", (long long)px, (long long)py);
    return;
  }

  Point d = p - c;
  double ld = dist(p, c);
  // assert(ld > 1e-6);
  d.x /= ld, d.y /= ld;
  d.x *= r, d.y *= r;
  Point o = d + c;
  Point t(-d.y, d.x);

  std::pair<ll, std::pair<ll, ll>> ans(ll(1e30), {-1e18 -1, -1e18-1});
  auto upd = [&](ll ox, ll oy) {
    if (sqr(ox - cx) + sqr(oy - cy) <= sqr(r))
      ans = std::min(ans, decltype(ans)(sqr(ox - px) + sqr(oy - py), {ox, oy}));
  };

  for (int i = -1e5; i <= 1e5; i++) {
    Point to = t;
    to.x *= i, to.y *= i;
    to = o + to;

    for (int u = -1; u <= 1; u++)
      for (int v = -1; v <= 1; v++) {
        ll ox = (ll)to.x + u;
        ll oy = (ll)to.y + v;
        upd(ox, oy);
      }
  }
  
  auto [ox, oy] = ans.second;
  printf("1\n%lld %lld %lld %lld\n", (long long)px, (long long)py, (long long)ox, (long long)oy);
}

signed main() {
  int T;
  scanf("%d", &T);
  while (T--) solve();
  return 0;
}
/*
1
0 0 500000000 1000000000 0
*/

詳細信息

Test #1:

score: 100
Accepted
time: 12ms
memory: 3696kb

input:

3
1 2 1 1 2
3 2 5 -10 3
0 0 1 10 0

output:

0
1 2
1
-10 3 -2 2
1
10 0 1 0

result:

ok correct (3 test cases)

Test #2:

score: 0
Accepted
time: 1ms
memory: 3692kb

input:

1
0 0 1 0 0

output:

0
0 0

result:

ok correct (1 test case)

Test #3:

score: 0
Accepted
time: 454ms
memory: 3776kb

input:

100
-1 0 2 -3 -2
0 -2 2 -2 0
2 -1 1 0 1
-1 -3 1 -1 0
-1 2 2 -1 -1
2 -2 2 0 -3
-2 -3 2 -3 -2
0 1 2 2 1
-1 0 1 -2 -2
2 -2 2 -1 -2
1 2 2 -2 2
-1 2 1 -1 2
-2 1 2 -3 -2
-1 1 1 -1 1
2 2 1 1 -3
2 0 1 -2 -1
-1 2 1 -2 0
2 -2 2 -2 -1
-2 -2 1 1 -2
-1 1 2 2 1
2 -3 1 0 -1
-3 -3 2 2 -1
2 1 1 -1 1
-3 -2 1 -2 -3
0 ...

output:

1
-3 -2 -2 -1
1
-2 0 -1 -1
1
0 1 1 -1
1
-1 0 -1 -2
1
-1 -1 -1 0
1
0 -3 0 -2
0
-3 -2
0
2 1
1
-2 -2 -1 -1
1
-1 -2 0 -2
1
-2 2 -1 2
0
-1 2
1
-3 -2 -2 -1
0
-1 1
1
1 -3 2 1
1
-2 -1 1 0
1
-2 0 -1 1
1
-2 -1 0 -2
1
1 -2 -1 -2
1
2 1 1 1
1
0 -1 1 -3
1
2 -1 -1 -3
1
-1 1 1 1
1
-2 -3 -3 -3
0
-2 -2
0
-2 -2
0
1 -1...

result:

ok correct (100 test cases)

Test #4:

score: -100
Wrong Answer
time: 482ms
memory: 3704kb

input:

100
-5 9 1 -2 -7
3 1 6 9 2
-2 -1 2 -7 3
-10 -8 7 -8 6
0 3 9 -6 -7
6 4 9 -1 4
8 6 7 -7 7
3 -7 7 2 0
-5 -1 6 -7 -7
-5 8 7 -9 -6
-6 -5 5 -10 -9
-7 1 9 7 -2
-4 9 4 8 3
3 -9 6 2 -2
-1 -7 3 -8 2
-2 -5 4 -1 0
1 2 9 -5 5
0 9 5 -4 -1
-10 8 2 -3 -7
-8 -3 3 2 -3
3 3 7 -4 6
6 0 6 -3 5
-7 5 9 9 9
2 0 2 8 -10
2 1...

output:

1
-2 -7 -5 8
1
9 2 8 2
1
-7 3 -4 -1
1
-8 6 -10 -1
1
-6 -7 -4 -5
0
-1 4
1
-7 7 1 6
1
2 0 2 -1
1
-7 -7 -7 -6
1
-9 -6 -5 1
1
-10 -9 -10 -8
1
7 -2 2 1
1
8 3 -1 7
1
2 -2 3 -3
1
-8 2 -3 -5
1
-1 0 -2 -1
0
-5 5
1
-4 -1 -2 5
1
-3 -7 -10 6
1
2 -3 -5 -3
1
-4 6 -3 6
1
-3 5 1 3
1
9 9 1 8
1
8 -10 2 -2
1
7 -1 5 1
...

result:

wrong answer the distance of your solution has travelled is longer than expected. (test case 18)