QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#750666 | #9576. Ordainer of Inexorable Judgment | UESTC_DECAYALI# | WA | 0ms | 3968kb | C++17 | 3.5kb | 2024-11-15 15:24:19 | 2024-11-15 15:24:19 |
Judging History
你现在查看的是最新测评结果
- [2024-12-23 14:23:26]
- hack成功,自动添加数据
- (/hack/1303)
- [2024-12-06 11:32:56]
- hack成功,自动添加数据
- (/hack/1271)
- [2024-11-15 15:24:19]
- 提交
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
using LD = long double;
const LD eps = 1e-8;
const LD PI = acosl(-1.0L);
LD sqr(LD x) {return x*x;}
int sgn(LD x) {return fabs(x)<=eps ? 0 : (x>eps ? 1 : -1);}
struct Point {
LD x, y;
LD operator^(const Point &b) const {return x*b.y - y*b.x;}
LD operator*(const Point &b) const {return x*b.x + y*b.y;}
bool operator<(const Point &b) const {return sgn((*this)^b) > 0;}
Point operator*(const LD &b) const {return Point{x*b, y*b};}
Point operator+(const Point &b) const {return Point{x+b.x, y+b.y};}
Point operator-(const Point &b) const {return Point{x-b.x, y-b.y};}
LD len() const {return sqrtl(x*x+y*y);}
LD len2() const {return x*x+y*y;}
Point rot(const LD &cosr, const LD &sinr) {
return {x*cosr - y*sinr, x*sinr + y*cosr};
}
LD ang(const Point &a) const {
return atan2l((*this)^a, (*this)*a);
}
};
LD p_seg_dis2(Point p, Point a, Point b) {
if (sgn((p-a)*(b-a))<=0 && sgn((p-b)*(a-b))<=0)
return min((a-p).len2(), (b-p).len2());
Point v = b-a;
LD res = abs(v ^ (p-a)) / v.len();
return sqr(res);
}
struct Circle {
Point c;
LD r;
pair<Point, Point> tangent(const Point &a) const {
Point e = a-c;
e = e * (r / e.len());
const LD costh = r / (c-a).len(), sinth = sqrtl(1 - sqr(costh));
const Point t1 = c + e.rot(costh, -sinth), t2 = c + e.rot(costh, sinth);
return {t1, t2};
}
};
int n, xx0, yy0, d;
LD t;
Circle cir;
vector<Point> conv;
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cout << setiosflags(ios::fixed) << setprecision(12);
cin >> n >> xx0 >> yy0 >> d >> t;
cir = Circle{{0.0L, 0.0L}, (LD)d};
conv.reserve(n);
for (int i=0; i<n; ++i) {
int x, y; cin >> x >> y;
conv.push_back(Point{(LD)x, (LD)y});
}
bool ok = false;
for (int i=0; i<n; ++i) {
if (sgn(sqr(d) - p_seg_dis2({0, 0}, conv[i], conv[(i+1)%n])) >= 0) {
ok = true; break;
}
}
bool flag = true;
for (int i=0; i<n; ++i) {
if (sgn((conv[(i+1)%n]-conv[i])^(Point{0, 0}-conv[i])) < 0) {
flag = false; break;
}
}
if (flag) ok=true;
if (ok) {
cout << t << '\n';
return 0;
}
vector<Point> vt1, vt2;
for (int i=0; i<n; ++i) {
auto [t1, t2] = cir.tangent(conv[i]);
vt1.push_back(t1);
vt2.push_back(t2);
}
auto findmn = [&](vector<Point> &vec){
auto res = vec[0];
for (auto p : vec) res = min(res, p);
return res;
};
auto findmx = [&](vector<Point> &vec){
auto res = vec[0];
for (auto p : vec) res = max(res, p);
return res;
};
auto t1 = findmx(vt1);
auto t2 = findmn(vt2);
auto rt1 = t1.rot(0, 1), rt2 = t2.rot(0, -1);
LD ang = rt2.ang(rt1);
LD ans = 0.0L;
int round = floor(t / (2*PI) + eps);
ans += round * ang;
t -= round*2*PI;
Point v = Point{xx0, yy0};
LD th2 = v.ang(rt2); if (sgn(th2) < 0) th2 = 2*PI+th2;
LD th1 = v.ang(rt1); if (sgn(th1) < 0) th1 = 2*PI+th1;
// printf("th2=%Lf th1=%Lf\n", th2, th1);
if (sgn(rt2^v)>0 && sgn(v^rt1)>0) {
if (t < th1) ans += t;
else ans += th1 + (sgn(t-th2)>=0 ? t-th2 : 0);
} else {
if (t > th2) ans += min(th1, t) - th2;
}
cout << ans << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3832kb
input:
3 1 0 1 1 1 2 2 1 2 2
output:
1.000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
3 1 0 1 2 1 2 2 1 2 2
output:
1.570796326795
result:
ok found '1.5707963', expected '1.5707963', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
3 1 0 1 10000 1 2 2 1 2 2
output:
2500.707752257475
result:
ok found '2500.7077523', expected '2500.7077523', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
3 10000 10000 1 10000 10000 9999 10000 10000 9999 10000
output:
0.384241300290
result:
ok found '0.3842413', expected '0.3842413', error '0.0000000'
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3968kb
input:
3 -10000 -10000 10000 10000 -10000 -9999 -10000 -10000 -9999 -10000
output:
10000.000000000000
result:
wrong answer 1st numbers differ - expected: '2500.2406700', found: '10000.0000000', error = '2.9996150'