QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#783426 | #8863. Attendance | alexhamidi | TL | 0ms | 0kb | C++20 | 1.9kb | 2024-11-26 09:45:24 | 2024-11-26 09:45:30 |
Judging History
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;
}
详细
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....