QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#758277 | #9576. Ordainer of Inexorable Judgment | arnold518# | WA | 1ms | 4448kb | C++17 | 3.7kb | 2024-11-17 17:24:43 | 2024-11-17 17:24:45 |
Judging History
你现在查看的是最新测评结果
- [2024-12-23 14:23:26]
- hack成功,自动添加数据
- (/hack/1303)
- [2024-12-06 11:32:56]
- hack成功,自动添加数据
- (/hack/1271)
- [2024-11-17 17:24:43]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long lint;
#define double long double
using point = pair<double, double>;
#define x first
#define y second
const double eps = 1e-10;
const double pi = 3.1415926535897932;
point operator+(point a, point b) { return point(a.x + b.x, a.y + b.y); }
point operator-(point a, point b) { return point(a.x - b.x, a.y - b.y); }
point operator*(double x, point a) { return point(x*a.x, x*a.y); }
double operator*(point a, point b) { return a.x * b.x + a.y * b.y; }
double operator/(point a, point b) { return a.x * b.y - a.y * b.x; }
int ccw(point p, point q, point r) {
double x = (q-p) / (r-p);
return (x > eps) - (x < -eps);
}
bool point_on_line(point p, point q, point r) {
double x = (r-p) * (q-p);
return ccw(p, q, r) == 0 and -eps < x and x < (q-p)*(q-p) + eps;
}
point intersect(point p, point u, point q, point v) {
return p + (((q-p) / v) / (u / v)) * u;
}
int line_intersect_verbose(point p, point q, point r, point s, point& a, point& b) {
if (ccw(p, q, r) == 0 and ccw(p, q, s) == 0) {
double u = (r-p) * (q-p);
double v = (s-p) * (q-p);
double l = (q-p) * (q-p);
if (u > v) swap(u, v);
if (l < u - eps or 0 > v + eps) return 0;
else if (abs(u-l) < eps) { a = p; return 1; }
else if (abs(0-v) < eps) { a = q; return 1; }
else {
a = p + (max((double)0.0, u) / l) * (q - p);
b = p + (min(l, v) / l) * (q - p);
return 3;
}
}
if (point_on_line(r, s, p)) { a = p; return 1; }
if (point_on_line(r, s, q)) { a = q; return 1; }
if (point_on_line(p, q, r)) { a = r; return 1; }
if (point_on_line(p, q, s)) { a = s; return 1; }
if (ccw(p, q, r) * ccw(p, q, s) < 0 and ccw(r, s, p) * ccw(r, s, q) < 0) {
a = intersect(p, q-p, r, s-r);
return 2;
}
return 0;
}
int N, D, T;
double th0;
point a[104];
bool able(double theta) {
for (int i=0; i<N; i++) {
if (abs(a[i].y * cos(theta) - a[i].x * sin(theta)) <= D
and a[i].x * cos(theta) + a[i].y * sin(theta) >= 0) return true;
}
point _a, _b;
for (int i=0; i<N; i++) {
point p1(-D * sin(theta), D * cos(theta));
point p2 = p1 + 100000 * point(cos(theta), sin(theta));
if (line_intersect_verbose(a[i], a[i+1], p1, p2, _a, _b) > 0) return true;
}
for (int i=0; i<N; i++) {
point p1(D * sin(theta), -D * cos(theta));
point p2 = p1 + 100000 * point(cos(theta), sin(theta));
if (line_intersect_verbose(a[i], a[i+1], p1, p2, _a, _b) > 0) return true;
}
return false;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
int x0, y0;
cin >> N >> x0 >> y0 >> D >> T;
th0 = atan2(y0, x0);
for (int i=0; i<N; i++) cin >> a[i].x >> a[i].y;
a[N] = a[0];
double th = atan2(a[0].y, a[0].x);
double L, R;
{
double l = th, r = th + pi;
for (int _=0; _<100; _++) {
double m = (l+r) / 2;
if (able(m)) l = m;
else r = m;
}
R = r;
}
{
double l = th - pi, r = th;
for (int _=0; _<100; _++) {
double m = (l+r) / 2;
if (able(m)) r = m;
else l = m;
}
L = l;
}
int revol = (int)(floor(T / (2*pi)) + eps);
double ans = revol * (R - L);
double t = T - revol * (2*pi);
if (R < th0) {
L += 2 * pi;
R += 2 * pi;
}
if (L <= th0 and th0 <= R) {
ans += min(R - th0, t);
ans += max((double)0.0, t - (L + 2*pi - th0));
} else {
ans += min(R-L, max((double)0.0, t - (L - th0)));
}
cout << fixed << setprecision(14);
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4248kb
input:
3 1 0 1 1 1 2 2 1 2 2
output:
1.00000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4200kb
input:
3 1 0 1 2 1 2 2 1 2 2
output:
1.57079632679490
result:
ok found '1.5707963', expected '1.5707963', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 4152kb
input:
3 1 0 1 10000 1 2 2 1 2 2
output:
2500.70775225747701
result:
ok found '2500.7077523', expected '2500.7077523', error '0.0000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 4352kb
input:
3 10000 10000 1 10000 10000 9999 10000 10000 9999 10000
output:
0.38424130029027
result:
ok found '0.3842413', expected '0.3842413', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4240kb
input:
3 -10000 -10000 10000 10000 -10000 -9999 -10000 -10000 -9999 -10000
output:
2500.24067000960847
result:
ok found '2500.2406700', expected '2500.2406700', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4208kb
input:
4 1 0 1 10000 -2 3400 -4 10000 -4 -10000 -2 -3400
output:
4999.21911540874298
result:
ok found '4999.2191154', expected '4999.2191154', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 4172kb
input:
4 1 0 1 10000 -2 3300 -4 10000 -4 -10000 -2 -3300
output:
4999.20039185481495
result:
ok found '4999.2003919', expected '4999.2003919', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 4448kb
input:
4 -3040 2716 2147 2 -9033 -8520 -8999 -8533 -8988 -8511 -9004 -8495
output:
0.35083005834207
result:
ok found '0.3508301', expected '0.3508301', error '0.0000000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 4332kb
input:
3 8168 -766 1549 1256 -3951 -6425 -3874 -6439 -3911 -6389
output:
84.83286116100695
result:
ok found '84.8328612', expected '84.8328612', error '0.0000000'
Test #10:
score: 0
Accepted
time: 1ms
memory: 4356kb
input:
8 2977 -3175 8766 2 -4868 7759 -4867 7925 -4867 7950 -4886 7952 -4979 7953 -5048 7877 -5003 7761 -4936 7759
output:
0.32786064690611
result:
ok found '0.3278606', expected '0.3278606', error '0.0000000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 4276kb
input:
13 -1715 -4640 267 8651 272 6659 264 6660 208 6664 108 6625 107 6621 93 6564 90 6551 90 6485 124 6474 219 6477 283 6525 288 6591 286 6657
output:
153.58962278468228
result:
ok found '153.5896228', expected '153.5896228', error '0.0000000'
Test #12:
score: 0
Accepted
time: 1ms
memory: 4372kb
input:
8 -9743 -7629 775 7 -194 981 -191 1720 -193 1845 -705 1929 -959 1950 -1131 1894 -1151 1604 -1031 1020
output:
2.04600620435563
result:
ok found '2.0460062', expected '2.0460062', error '0.0000000'
Test #13:
score: -100
Wrong Answer
time: 1ms
memory: 4308kb
input:
9 -6770 -1426 3491 1918 -2118 2886 -2063 3245 -2122 3709 -2129 3737 -2850 3718 -2984 3650 -3042 3462 -3028 2972 -2688 2888
output:
822.03886777323359
result:
wrong answer 1st numbers differ - expected: '822.2411850', found: '822.0388678', error = '0.0002461'