QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#754086 | #9576. Ordainer of Inexorable Judgment | ucup-team4906# | WA | 0ms | 3904kb | C++17 | 4.9kb | 2024-11-16 14:11:48 | 2024-11-16 14:11:49 |
Judging History
你现在查看的是最新测评结果
- [2024-12-23 14:23:26]
- hack成功,自动添加数据
- (/hack/1303)
- [2024-12-06 11:32:56]
- hack成功,自动添加数据
- (/hack/1271)
- [2024-11-16 14:11:48]
- 提交
answer
#include<bits/stdc++.h>
#define F(i, a, b) for(int i = a; i <= b; i ++)
using namespace std;
using vi = vector<int>;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
typedef unsigned long long ull;
#define N 110
typedef double T;
typedef double db;
const db pi = acosl(-1);
const db eps = 1e-8;
int sgn(T x) {
if(fabs(x) < eps) return 0;
else return x < 0 ? -1 : 1;
}
struct point {
T x, y;
point() {}
point(T x, T y) : x(x), y(y) {}
point operator + (point B) const {return point(x + B.x, y + B.y);}
point operator - (point B) const {return point(x - B.x, y - B.y);}
point operator * (T k) const {return point(x * k, y * k);}
point operator / (T k) const {return point(x / k, y / k);}
bool operator == (point B) const {return sgn(x - B.x) == 0 && sgn(y - B.y) == 0;}
bool operator < (point B) const {return sgn(x - B.x) < 0 || (sgn(x - B.x) == 0 && sgn(y - B.y) < 0);}
T cross(point p) const {return x * p.y - y * p.x;}
int left(point p) const {return sgn(cross(p));}
T len() const {return sqrtl(x * x + y * y);}
point rot(long double cosr, long double sinr) {return point(x * cosr - y * sinr, x * sinr + y * cosr);}
};
T dot(point x) {return x.x * x.x + x.y * x.y;}
db dis(point A, point B) {return sqrtl((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));}
int get_region(point p) {
return sgn(p.y) < 0 ? -1 : sgn(p.y) > 0 | (sgn(p.y) == 0 & sgn(p.x) < 0);
}
bool cmp_arg(point a, point b) {
int p = get_region(a), q = get_region(b);
if(p != q) return p < q;
if(a.left(b) == 0) return dot(a) < dot(b);
return a.left(b) == 1;
}
int n, x0, Y0, d, t;
point o(0, 0);
pair<point, point> tangent(const point a) {
point e = a; e = e / e.len() * d;
long double costh = d / dis(a, o), sinth = sqrtl(1 - costh * costh);
point t1 = o + e.rot(costh, -sinth), t2 = o + e.rot(costh, sinth);
// 两个切点
return {t1, t2};
}
bool cmp(pair<point, pair<point, int>> x1, pair<point, pair<point, int>> x2) {
return cmp_arg(x1.first, x2.first);
}
point rotate(point A, T rad) {
return point(A.x * cosl(rad) - A.y * sinl(rad), A.x * sinl(rad) + A.y * cosl(rad));
}
db dot(point A, point B) {return A.x * B.x + A.y * B.y;}
db len(point A) {return sqrtl(dot(A, A));}
db angle(point A, point B) {
db tmp = dot(A, B) / len(A) / len(B);
if(tmp > 1) tmp = 1;
else if(tmp < -1) tmp = -1;
db res = acosl(tmp);
// cout << res << "QAQ\n";
// cout << A.x << " " << A.y << " " << B.x << " " << B.y << " " << B.left(A) << "????\n";
if(B.left(A) == 1) res = 2 * pi - res;
return res;
}
void sol() {
cout << fixed << setprecision(10);
cin >> n >> x0 >> Y0 >> d >> t;
vector<point> p;
vector<pair<point, pair<point, int>>> qaq;
F(i, 0, n - 1) {
int x, y; cin >> x >> y;
p.push_back(point(x, y));
auto [u, v] = tangent(point(x, y));
qaq.push_back({point(x, y) - u, {u, i}}), qaq.push_back({point(x, y) - v, {v, i}});
}
sort(qaq.begin(), qaq.end(), cmp);
point st, ed;
int cnt = 0;
for(int i = 0; i < qaq.size(); i ++) if(qaq[i].first.left(qaq[(i + 1) % qaq.size()].first) == -1) {
cnt ++;
point u = qaq[(i + 1) % qaq.size()].second.first;
point v = qaq[i].second.first;
// cout << u.x << " " << u.y << "!!!\n";
// cout << v.x << " " << v.y << "???\n";
st = rotate(u, pi * 1.5), ed = rotate(v, pi / 2.0);
// st = rotate(u, pi / 2.0), ed = rotate(v, pi * 1.5);
}
assert(cnt == 1);
point S(x0, Y0);
S = S / S.len() * d;
// cout << st.x << " " << st.y << "??\n";
// cout << ed.x << " " << ed.y << "??\n";
// cout << S.x << " " << S.y << "!!\n";
int l = 0, r = 100000;
while(l < r) {
int mid = l + r + 1 >> 1;
if(sgn(mid * 2.0 * pi - t) <= 0) l = mid;
else r = mid - 1;
}
// cout << l << "???\n";
// cout << l << "Q\n";
// cout << angle(st, ed) << "::\n";
long double res = angle(st, ed) * l;
// cout << res << "!!\n";
t -= l * (2.0 * pi);
if(S.left(st) > 0 && ed.left(S) > 0) {
if(sgn(t - angle(S, ed)) <= 0) res += t;
else {
t -= angle(S, ed);
res += angle(S, ed);
if(sgn(t - angle(ed, st)) > 0) {
res += t - angle(ed, st);
}
}
} else {
// cout << ">>\n";
if(sgn(t - angle(S, st)) > 0) {
t -= angle(S, st);
if(sgn(t - angle(st, ed)) > 0) res += angle(st, ed);
else res += t;
}
}
cout << res << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
while (T --) sol();
return 0;
}
/*
3 1 0 1 1
1 2
2 1
2 2
3 1 0 1 2
1 2
2 1
2 2
3 1 0 1 10000
1 2
2 1
2 2
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3904kb
input:
3 1 0 1 1 1 2 2 1 2 2
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
3 1 0 1 2 1 2 2 1 2 2
output:
1.5707963268
result:
ok found '1.5707963', expected '1.5707963', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
3 1 0 1 10000 1 2 2 1 2 2
output:
2500.7077522575
result:
ok found '2500.7077523', expected '2500.7077523', error '0.0000000'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3844kb
input:
3 10000 10000 1 10000 10000 9999 10000 10000 9999 10000
output:
0.3841205839
result:
wrong answer 1st numbers differ - expected: '0.3842413', found: '0.3841206', error = '0.0001207'