QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#783426#8863. AttendancealexhamidiTL 0ms0kbC++201.9kb2024-11-26 09:45:242024-11-26 09:45:30

Judging History

This is the latest submission verdict.

  • [2024-11-26 09:45:30]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 0kb
  • [2024-11-26 09:45:24]
  • Submitted

answer

#include <iostream>
#include <cmath>
#include <numbers>

using namespace std;

int sq(int a) {
    return a * a;
}

double sq(double a) {
    return a * a;
}


double getDistance(pair<double, double> p1, pair<double, double> p2) {
    auto [x1, y1] = p1;
    auto [x2, y2] = p2;
    return sqrt(sq(x1-x2) + sq(y1-y2));
}

bool lineOnCircle(int x1, int y1, int x2, int y2, int xc, int yc, int r) {
    int a = sq(x2-x1) + sq(y2-y1);
    int b = 2 * (((x2 - x1) * (x1 - xc)) + ((y2 - y1) * (y1 - yc)));
    int c = sq(x1-xc) + sq(y1-yc) - sq(r);
    int disc = sq(b) - 4 * a * c;
    return (disc >= 0);
}

const int BS_ITERS = 10000;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int xa, ya, xb, yb, xc, yc, r;
        cin >> xa >> ya >> xb >> yb >> xc >> yc >> r;
        pair<int, int> a = {xa, ya};
        pair<int, int> b = {xb, yb};
        double ans;
        double theta = M_PI/2;
        pair<double, double> currPos = {xc, yc+r};
        for (int _ = 0; _ < BS_ITERS; _++) {
            auto [currX, currY] = currPos;

            double relX = currX-xc;
            double relY = currY-yc;

            pair<double, double> ccw = {xc + (relX*cos(theta)-relY*sin(theta)),
                                        yc + (relX*sin(theta)+relY*cos(theta))};

            pair<double, double> cw = {xc + (relX*cos(-theta)-relY*sin(-theta)),
                                        yc + (relX*sin(-theta)+relY*cos(-theta))};

            double ccwD = getDistance(a, ccw) + getDistance(b, ccw);
            double cwD = getDistance(a, cw) + getDistance(b, cw);

            if (ccwD < cwD) {
                currPos = ccw;
            } else {
                currPos = cw;
            }
            theta /= 2;
            ans = getDistance(a, currPos) + getDistance(b, currPos);
        }
        cout << ans << "\n";
    }


    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

300000
0 3
2 5
4 7
6 9
8 11
10 13
12 15
14 17
16 19
18 21
20 23
22 25
24 27
26 29
28 31
30 33
32 35
34 37
36 39
38 41
40 43
42 45
44 47
46 49
48 51
50 53
52 55
54 57
56 59
58 61
60 63
62 65
64 67
66 69
68 71
70 73
72 75
74 77
76 79
78 81
80 83
82 85
84 87
86 89
88 91
90 93
92 95
94 97
96 99
98 101
1...

output:

3.51472
21.5147
31.5147
49.5147
59.5147
77.5147
87.5147
105.515
115.515
133.515
143.515
161.515
171.515
189.515
199.515
217.515
227.515
245.515
255.515
273.515
283.515
301.515
311.515
329.515
339.515
357.515
367.515
385.515
395.515
413.515
423.515
441.515
451.515
469.515
479.515
497.515
507.515
525....

result: