QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#137484#2350. Integer CowVengeful_Spirit#RE 1ms3584kbC++203.4kb2023-08-10 13:19:092023-08-10 13:19:11

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:19:11]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3584kb
  • [2023-08-10 13:19:09]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const double EPS = 1e-8;
struct Point {
    double x, y;
};
double Dis(const Point &p1, const Point &p2) {
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
Point Get(const Point &c, double r, const Point &p) {
    Point u, v;
    if(Dis(p, c) < EPS) return p;
    // cerr << c.x << " " << c.y << " "<< r << "\n";
    // cerr << p.x << " "<< p.y <<"\n";
    // cerr << Dis(p, c) << "\n";
    u.x = c.x + r * fabs(c.x - p.x) / Dis(c, p);
    u.y = c.y + r * fabs(c.y - p.y) / Dis(c, p) * ((c.x - p.x) * (c.y - p.y) < 0 ? -1 : 1);
    v.x = c.x - r * fabs(c.x - p.x) / Dis(c, p);
    v.y = c.y - r * fabs(c.y - p.y) / Dis(c, p) * ((c.x - p.x) * (c.y - p.y) < 0 ? -1 : 1);
    // cerr << u.x << " " << u.y << " " << v.x << " " << v.y << "\n";
    return Dis(u, p) < Dis(v, p) ? u : v;
}

pair<double, double> get(double x, double y, double r2, double X) {
    double delta = r2 - (X - x) * (X - x);
    if(delta < 0) return {0, -1};
    delta = sqrt(delta);
    return {y - delta, y + delta};
}

pair<double, double> in(pair<double, double> x, pair<double, double> y) {
    if(x.first == 0 && x.second == -1) return {0, -1};
    if(y.first == 0 && y.second == -1) return {0, -1};
    if(x.first > y.first) swap(x, y);
    if(y.second <= x.second) return y;
    if(y.first > x.second) return {0, -1};
    return {y.first, x.second};
}

void solve() {
    ll xc, yc, R, x, y;
    cin >> xc >> yc >> R >> x >> y;
    x -= xc, y -= yc;
    if(!x && !y) {
        cout << "0\n" << xc << " " << yc << "\n";
        return ;
    }
    // (0, 0) r, x, y;
    int flg = 0;
    ll sx = 0, sy = 0;
    double dis = sqrt(x * x + y * y) - R;
    // cerr << dis << "\n";
    // return ;
    double mx = (dis + 1) * (dis + 1);
    // cerr << mx << "\n";
    ll ans = 9e18;
    ll L, RR;
    int ff = 0;
    Point st; st.x = x, st.y = y;
    double jx = Get((Point){0, 0}, R, st).x;
    // cerr << jx << "\n";
    ll l = -2e9, r = jx;
    while(l <= r) {
        ll mid = (l + r) >> 1;
        auto[ll, rr] = in(get(0, 0, R * R, mid), get(x, y, mx, mid));
        if(ll == 0 && rr == -1) {
            l = mid + 1;
        }
        else {
            ff = 1;
            // cerr << mid << " " << ll << " "<< rr << "\n";
            L = mid, r = mid - 1;
        }
    }
    assert(ff);
    l = (jx + 0.5), r = 2e9;
    while(l <= r) {
        ll mid = (l + r) >> 1;
        auto[ll, rr] = in(get(0, 0, R * R, mid), get(x, y, mx, mid));
        if(ll == 0 && rr == -1) r = mid - 1;
        else {
            ff = 1;
            // cerr << "!" << mid << " "<< ll << " " << rr << "\n";
            RR = mid, l = mid + 1;
        }
    }
    // cerr << L << " " << RR << "\n";
    // return ;
    for(ll i = L; i <= RR; ++i) {
        auto[l, r] = in(get(0, 0, R * R, i), get(x, y, mx, i));
        for(ll j = 1ll * l; j <= r; ++j) {
            if((x - i) * (x - i) + (y - j) * (y - j) <= mx) {
                flg = 1;
                mx = (x - i) * (x - i) + (y - j) * (y - j);
                sx = i, sy = j;
            }
        }
    }
    assert(flg);
    cout << 1 << "\n" << x + xc << " " << y + yc << " " << sx + xc << " " << sy + yc << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T; cin >> T;
    for(int o = 1; o <= T; ++o) {
        solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3416kb

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: 3584kb

input:

1
0 0 1 0 0

output:

0
0 0

result:

ok correct (1 test case)

Test #3:

score: -100
Dangerous Syscalls

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:


result: