QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#728941 | #9576. Ordainer of Inexorable Judgment | ucup-team5062# | WA | 1ms | 4248kb | C++17 | 3.0kb | 2024-11-09 16:14:56 | 2024-11-09 16:14:57 |
Judging History
你现在查看的是最新测评结果
- [2024-12-23 14:23:26]
- hack成功,自动添加数据
- (/hack/1303)
- [2024-12-06 11:32:56]
- hack成功,自动添加数据
- (/hack/1271)
- [2024-11-14 21:58:28]
- hack成功,自动添加数据
- (/hack/1181)
- [2024-11-09 16:14:56]
- 提交
answer
#include <array>
#include <cmath>
#include <vector>
#include <complex>
#include <iostream>
#include <algorithm>
using namespace std;
const long double pi = acos(-1.0L);
using point = complex<long double>;
long double dot(const point& a, const point& b) {
return (conj(a) * b).real();
}
long double cross(const point& a, const point& b) {
return (conj(a) * b).imag();
}
array<point, 2> tangent(const point& p, const point& c, double r) {
point v = (p - c) / abs(p - c);
long double d = abs(p - c);
long double t = r * r / d;
array<point, 2> res;
res[0] = c + (t - point(0, 1) * sqrt(r * r - t * t)) * v;
res[1] = c + (t + point(0, 1) * sqrt(r * r - t * t)) * v;
return res;
}
// half-line: (0, 0) towards z
// segment: s0-s1
bool intersect(const point& z, const point& s0, const point& s1) {
point v0 = s0, v1 = s1;
long double t0 = cross(z, v0);
long double t1 = cross(z, v1);
if (t0 > t1) {
swap(t0, t1);
swap(v0, v1);
}
if (t0 > 0 || t1 < 0) {
return false;
}
if (t0 == 0 && dot(z, v0) >= 0) {
return true;
}
if (t1 == 0 && dot(z, v1) >= 0) {
return true;
}
if (t0 == 0 || t1 == 0) {
return false;
}
return cross(v0, v1) > 0;
}
// half-line: (0, 0) towards z
// point: p
long double distance(const point& z, const point& p) {
if (dot(z, p) < 0) {
return abs(p);
}
return abs(cross(z, p)) / abs(z);
}
// half-line: (0, 0) towards z
// segment: s0-s1
long double distance(const point& z, const point& s0, const point& s1) {
if (intersect(z, s0, s1)) {
return 0.0;
}
long double res1 = distance(z, s0);
long double res2 = distance(z, s1);
return min(res1, res2);
}
int main() {
// step #1. input
auto read_point = []() -> point {
long double x, y;
cin >> x >> y;
return point(x, y);
};
int N, D, T;
cin >> N;
point V = read_point();
cin >> D >> T;
vector<point> G(N);
for (int i = 0; i < N; i++) {
G[i] = read_point();
}
G.push_back(G[0]);
// step #2. calculate candidates
vector<long double> v;
for (int i = 0; i < N; i++) {
array<point, 2> res = tangent(G[i], point(0, 0), D);
v.push_back(arg(res[0]));
v.push_back(arg(res[1]));
}
sort(v.begin(), v.end());
v.push_back(v[0] + 2 * pi);
// step #3. calculate "validity"
vector<bool> ok(2 * N, false);
for (int i = 0; i < 2 * N; i++) {
point z = polar(1.0L, (v[i] + v[i + 1]) / 2);
for (int j = 0; j < N; j++) {
long double d = distance(z, G[j], G[j + 1]);
if (d <= D) {
ok[i] = true;
}
}
}
// step #4. calculate answer
long double tl = arg(V);
long double tr = tl + T;
long double ans = 0.0;
for (int i = 0; i < 2 * N; i++) {
if (ok[i]) {
long double pl = v[i] - 2 * pi, pr = v[i + 1] - 2 * pi;
while (pl < tr) {
long double ql = max(pl, tl);
long double qr = min(pr, tr);
if (ql < qr) {
ans += qr - ql;
}
pl += 2 * pi;
pr += 2 * pi;
}
}
}
// step #5. output
cout.precision(15);
cout << fixed << ans << endl;
return 0;
}
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.000000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4180kb
input:
3 1 0 1 2 1 2 2 1 2 2
output:
1.570796326794897
result:
ok found '1.5707963', expected '1.5707963', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4176kb
input:
3 1 0 1 10000 1 2 2 1 2 2
output:
2500.707752257475330
result:
ok found '2500.7077523', expected '2500.7077523', error '0.0000000'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 4192kb
input:
3 10000 10000 1 10000 10000 9999 10000 10000 9999 10000
output:
4999.460466887865790
result:
wrong answer 1st numbers differ - expected: '0.3842413', found: '4999.4604669', error = '4999.0762256'