QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#137509 | #2350. Integer Cow | Rd_rainydays# | WA | 482ms | 3776kb | C++20 | 2.1kb | 2023-08-10 13:37:14 | 2023-08-10 13:37:17 |
Judging History
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)