QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#884381 | #9547. Two Convex Holes | UESTC_NLNS | WA | 97ms | 4096kb | C++20 | 6.4kb | 2025-02-06 02:29:45 | 2025-02-06 02:29:46 |
Judging History
answer
/*
L(0,0,z0)
z = z1 -> z=p <====> p * (z0 / (z0-z1)) = p * al
p = p0 + vt ------> p = p0 * al + vt * al
p1 : p1 * al1 + vt * al1 -------> p1 * al1
P2 : p2 * al2 + vt * al2 -------> pt * al2 + vt * (al2 - al1)
*/
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
using ldb = long double;
struct pt {
ldb x, y;
pt operator+(const pt& o) const { return {x + o.x, y + o.y}; };
pt operator-(const pt& o) const { return {x - o.x, y - o.y}; };
pt operator*(const ldb o) const { return {x * o, y * o}; };
ldb operator*(const pt& o) const { return o.x * x + o.y * y; }
ldb operator^(const pt& o) const { return x * o.y - y * o.x; }
};
pt rotate(const pt& a, const pt& v2) {
return {v2 * a, v2 ^ a};
}
struct seg {
pt a, b;
bool operator<(const seg& o) const {
if (a.y != o.a.y) a.y < o.a.y;
return b.y < o.b.y;
}
pt at(ldb y) const {
return (b * (y - a.y) + a * (b.y - y)) * (1 / (b.y - a.y));
}
};
struct poly {
ldb t, a0, a1, a2, a3;
bool operator<(const poly& o) const { return t < o.t; }
};
struct item {
ldb t, v1, v2;
};
int cnt = 0;
int t;
const ldb eps = 1e-9;
void solve() {
pt a0, v;
ldb z0, z1, z2;
cin >> a0.x >> a0.y >> z0 >> v.x >> v.y;
int n1, n2;
cin >> n1 >> z1;
vector<pt> c1(n1);
for (int i = 0; i < n1; ++i) cin >> c1[i].x >> c1[i].y;
cin >> n2 >> z2;
vector<pt> c2(n2);
for (int i = 0; i < n2; ++i) cin >> c2[i].x >> c2[i].y;
ldb alp1 = z0 / (z0 - z1);
ldb alp2 = z0 / (z0 - z2);
v = v * (alp1 - alp2);
ldb beta = v * v;
v = v * (1 / beta);
// v = rotate(v, v);
for (auto& u : c1) u = rotate((u - a0) * alp1, v);
for (auto& u : c2) u = rotate((u - a0) * alp2, v);
// for (const auto& u : c1) cout << u.x << " " << u.y << '\n';
// for (const auto& u : c2) cout << u.x << " " << u.y << '\n';
vector<seg> s1, s2, s3, s4;
for (int i = 0; i < n1; ++i) {
auto a = c1[i], b = c1[i == n1 - 1 ? 0 : i + 1];
if (abs(a.y - b.y) < eps) continue;
if (a.y > b.y)
s1.push_back({b, a});
else
s2.push_back({a, b});
}
for (int i = 0; i < n2; ++i) {
auto a = c2[i], b = c2[i == n2 - 1 ? 0 : i + 1];
if (abs(a.y - b.y) < eps) continue;
if (a.y > b.y)
s3.push_back({b, a});
else
s4.push_back({a, b});
}
sort(s1.begin(), s1.end());
sort(s2.begin(), s2.end());
sort(s3.begin(), s3.end());
sort(s4.begin(), s4.end());
vector<item> q;
auto update = [&](const seg& s, const seg& t, ldb z0, ldb z1, int f) -> void {
if (abs(z0 - z1) < eps) return;
auto a = s.at(z0), b = s.at(z1);
auto c = t.at(z0), d = t.at(z1);
ldb t1 = c.x - a.x, t2 = d.x - b.x;
if (t1 < t2) swap(t1, t2);
ldb val = z1 - z0;
if (abs(t1 - t2) > eps) {
q.push_back({t1, 0, f * val / (t2 - t1)});
q.push_back({t2, 0, -f * val / (t2 - t1)});
} else {
q.push_back({t2, f * val, 0});
}
};
int cc = 0;
for (const auto& s : {s3, s4}) {
for (const auto& t : {s1, s2}) {
cc++;
int f = cc == 1 || cc == 4 ? -1 : 1;
ldb lst_z = max(s[0].a.y, t[0].a.y);
for (int i = 0, j = 0; i < s.size() && j < t.size();) {
if (s[i].b.y < t[j].a.y) {
i++;
continue;
}
if (t[j].b.y < s[i].a.y) {
j++;
continue;
}
ldb nz = min(s[i].b.y, t[j].b.y);
update(s[i], t[j], lst_z, nz, f);
lst_z = nz;
if (nz == t[j].b.y)
j++;
else
i++;
}
}
}
sort(q.begin(), q.end(), [&](const item& a, const item& b) { return a.t < b.t; });
vector<poly> ans;
ldb v0 = 0, v1 = 0, s = 0, ss = 0;
ldb lt = -1e50;
ans.push_back({lt, s, v0, v1});
for (int i = 0; i < q.size(); ++i) {
auto t = q[i].t;
auto dt = t - lt;
ss += s * dt + v0 * dt * dt / 2 + v1 * dt * dt * dt / 6;
s += v0 * dt + v1 * dt * dt / 2;
v0 += v1 * dt;
v0 += q[i].v1, v1 += q[i].v2;
lt = t;
ans.push_back({q[i].t, ss, s, v0, v1});
}
auto query = [&](ldb t) -> ldb {
auto [lt, a0, a1, a2, a3] = *(--upper_bound(ans.begin(), ans.end(), poly{t, 0, 0, 0}));
t -= lt;
return a0 + a1 * t + a2 * t * t / 2 + a3 * t * t * t / 6;
};
auto query2 = [&](ldb t) -> ldb {
auto [lt, a0, a1, a2, a3] = *(--upper_bound(ans.begin(), ans.end(), poly{t, 0, 0, 0}));
t -= lt;
// cout << a0 << " " << a1 << a2 << a3 << '\n';
return a1 + a2 * t + a3 * t * t / 2;
};
// for (const auto [t, a0, a1, a2, a3] : ans) {
// cout << t << " : " << a0 << " " << a1 << " " << a2 / 2 << " " << a3 / 6 << '\n';
// }
int cq;
cin >> cq;
for (int i = 0; i < cq; ++i) {
ldb t1, t2;
cin >> t1 >> t2;
cnt++;
// if (cnt == 10156) {
// cout << a0.x << " " << a0.y << " " << z0;
// cnt++, cnt--;
// }
// t2 *= beta, t1 *= beta;
ldb result = t1 == t2 ? query2(t1) : (query(t2) - query(t1)) / (t2 - t1);
// cout << ans << '\n';
// if (!(-1e-6 <= result & result <= 1e50)) {
// printf("%.8d\n", cnt);
// }
printf("%.8LF\n", max(result * beta, (ldb)0));
}
}
int main() {
// freopen("m.in", "r", stdin);
cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
cin >> t;
while (t--) solve();
}
/*
1
0 0 3 0 -1
4 1
1 0
3 0
3 2
1 2
4 2
0 0
1 0
1 1
0 1
3
0 10
1 2
1 1
1
-10 -75 555 453 -988
8 388
-973 837
-723 -824
-500 -963
761 -967
982 -425
973 782
501 1000
-814 868
9 544
-982 306
-922 -411
-783 -924
808 -931
949 -870
963 -375
989 582
755 958
-978 619
1
59 59
59 91
16 62
5 37
16 16
10 69
11 85
3 73
8 18
46 80
20 85
43 78
26 71
51 66
42 68
49 76
22 65
18 28
67 86
1 57
72 97
72 80
59 100
46 94
79 79
40 80
32 68
17 77
64 86
10 56
47 89
51 75
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3968kb
input:
1 0 0 3 0 -1 4 1 1 0 3 0 3 2 1 2 4 2 0 0 1 0 1 1 0 1 3 0 10 1 2 1 1
output:
0.45000000 1.12500000 2.25000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
1 -5448 2169 9 731 -431 64 1 -7417 -2691 -7203 -4235 -6869 -6172 -6746 -6856 -6628 -7104 -5983 -7731 -5755 -7926 -4211 -8457 -3739 -8585 -3653 -8604 -2307 -8877 -998 -9109 -201 -9110 874 -9110 2692 -8754 2984 -8696 3438 -8597 3671 -8536 5152 -8058 5700 -7775 5892 -7619 6304 -7221 7388 -5673 7742 -51...
output:
910.01769215
result:
ok found '910.01769', expected '910.01769', error '0.00000'
Test #3:
score: 0
Accepted
time: 96ms
memory: 4096kb
input:
10000 -8 -1 6 -1 -5 3 1 -7 7 -6 -3 3 6 3 4 -7 3 10 -2 -7 4 5 5 7 1 1 0 0 0 5 1 8 -10 -4 10 -8 7 5 4 -9 1 -8 -7 4 -9 5 7 3 9 5 8 -8 4 2 -10 4 -8 10 1 8 9 7 3 9 1 3 7 9 6 10 3 9 0 1 3 3 -2 9 9 4 -3 3 4 -10 10 -6 -7 8 -5 3 5 -9 1 -2 -2 7 1 3 6 7 2 7 4 5 -10 4 7 -2 5 3 3 -10 7 -8 -9 -3 10 3 4 -9 9 2 -9 ...
output:
0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 52.81830481 70.18546919 71.04629333 0.00000000 0.00000000 0.00437583 7.27590435 2.24042406 4.43672518 0.00000000 0.39874735 24.30553792 1.28024232 0.00000000 0.00000000...
result:
ok 100000 numbers
Test #4:
score: 0
Accepted
time: 97ms
memory: 4096kb
input:
10000 7 2 9 -3 10 5 1 -10 8 -7 4 -4 1 0 -2 10 3 3 6 -10 10 -8 -4 7 -10 4 0 8 3 3 1 1 0 1 -9 3 10 -5 -3 3 3 -10 -7 3 -2 7 10 3 6 -9 1 -7 8 -8 10 2 5 9 6 7 -6 -8 9 -3 9 3 6 -1 -8 3 -10 3 -5 4 8 -9 -3 7 -6 9 6 -8 9 3 3 7 2 9 1 4 3 4 7 9 -6 4 1 -10 9 4 -10 7 -10 8 10 4 2 -10 1 2 -5 4 -3 3 4 4 6 6 2 7 6 ...
output:
0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 4.95238095 41.55555556 7.48011207 25.50528069 7.48011207 8.80551284 0.00000000 0.00000000 0.00000000 0.00000000 0.00242541 2.94767657 0.00000000 0.00000000 0.00000000 0.00000000 0.01212703 0.00000000 1.47383828 0.00000000 0...
result:
ok 100000 numbers
Test #5:
score: 0
Accepted
time: 97ms
memory: 3968kb
input:
10000 -7 8 9 6 10 5 2 -7 -1 -4 -7 3 -3 6 6 -7 5 4 8 -9 0 -4 -10 3 4 -4 4 6 3 8 5 7 7 8 8 10 0 5 6 6 7 -5 9 -3 -2 4 4 -3 3 8 -5 8 -4 7 7 4 7 -9 3 -6 -2 10 2 2 5 4 5 10 2 5 6 7 1 8 9 -7 9 8 -5 3 2 -7 7 -6 -1 1 5 5 4 -5 -9 5 -10 8 2 2 5 -3 3 9 5 6 8 9 0 2 4 6 0 0 3 3 4 7 2 3 2 7 -2 -7 7 -5 3 3 1 1 10 2...
output:
0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 51.20256420 0.00030551 51.24489796 27.54344756 0.00020368 41.40057950 10.31207967 0.00000000 0.00000000 5.53800246 0.00000000 0.00000000 0.00000000 0.01551879 0.9094697...
result:
ok 100000 numbers
Test #6:
score: 0
Accepted
time: 96ms
memory: 4096kb
input:
10000 3 7 10 -7 -3 5 2 -1 1 6 -7 8 -2 4 4 -1 6 3 8 -6 -3 -2 -7 -2 9 1 1 7 -2 -5 7 -5 5 3 1 -9 1 10 -7 8 9 3 6 -2 4 5 -6 6 10 5 2 10 5 7 4 10 1 2 1 5 -2 0 10 1 5 3 1 -4 10 7 3 3 6 3 2 -9 4 -4 -9 -6 0 2 3 4 3 10 2 4 10 -3 -6 3 1 -7 5 -5 -7 10 -3 5 7 -9 -6 -7 -9 2 -9 5 -7 0 -3 10 2 10 6 7 0 1 1 5 5 5 6...
output:
5.78434692 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 11.19071477 0.00000000 0.00074742 38.31115625 0.00000000 0.00000000 0.00000000 87.50823075 21.89208929 110.01600659 11.63000756 23.80839002 98.53961752 66.46031746 55.55291005 0.00000000 20.83234127 0.00000000 0....
result:
ok 100000 numbers
Test #7:
score: 0
Accepted
time: 95ms
memory: 4096kb
input:
10000 -7 -9 8 -2 -9 4 5 -8 -7 4 -9 5 8 -8 4 4 7 -7 2 0 -5 6 6 -6 9 3 8 10 4 6 2 5 -3 -2 10 10 -8 3 6 -9 0 -7 -6 4 7 5 9 -10 4 -6 -8 2 -8 -2 3 -8 4 2 2 5 6 10 -8 -7 9 2 5 4 2 -10 -4 9 -2 7 5 2 10 5 3 -8 6 -5 -9 9 -5 4 7 -4 7 1 8 8 -7 -7 10 7 7 4 5 -10 -8 6 -4 6 3 -2 8 4 8 -9 -9 8 8 6 8 -4 4 8 3 8 3 8...
output:
0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 108.99283521 5.56525573 5.56525573 49.86435902 0.00000000 142.98614459 0.00000000 79.07237302 62.33044878 17.97600676 0.00000000 36.31873696 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.000...
result:
ok 100000 numbers
Test #8:
score: 0
Accepted
time: 95ms
memory: 4096kb
input:
10000 7 -5 9 2 10 3 1 -2 2 9 -2 10 2 3 6 -10 -5 5 6 -5 10 1 5 5 -9 3 8 -9 -7 4 3 -10 -4 9 1 4 5 -8 8 3 7 -7 -2 9 -2 7 8 12 5 7 7 8 0 0 2 5 3 5 5 10 3 4 3 8 1 7 5 8 2 9 3 10 -5 0 9 -3 -8 5 4 -10 -2 3 -8 9 5 6 9 -5 8 4 8 -10 -3 6 -3 10 2 7 10 8 1 6 4 6 8 8 1 5 4 7 7 8 2 9 4 8 -10 -4 9 6 -5 5 5 3 -1 9 ...
output:
0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 19.57871462 0.00000000 0.00000000 40.19221698 6.69870283 0...
result:
ok 100000 numbers
Test #9:
score: 0
Accepted
time: 96ms
memory: 4096kb
input:
10000 -8 -5 4 -1 5 3 1 -3 -8 0 -5 2 5 4 2 -5 -5 9 7 9 10 -2 8 10 1 6 4 5 3 10 1 6 1 2 1 3 0 4 9 9 6 8 1 3 8 3 5 8 2 5 1 -7 -8 3 -7 -1 -2 -5 1 -7 -7 4 4 -4 -3 -1 -7 7 -8 -1 7 12 3 7 8 8 9 10 4 5 6 8 1 8 0 5 2 9 5 8 5 5 0 0 2 7 -1 8 10 -9 -7 6 1 -3 -6 1 -8 6 -7 6 -5 0 6 -2 5 4 5 -7 8 -6 -7 5 -3 2 9 9 ...
output:
6.12986040 0.00000000 0.02592593 6.12986040 19.98060034 15.23391026 11.08057812 0.00000000 0.00000000 15.23391026 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 25.80540436 30.96648523 0.00000000 0.00000000 0.000000...
result:
ok 100000 numbers
Test #10:
score: 0
Accepted
time: 97ms
memory: 4096kb
input:
10000 -2 -5 7 -3 6 3 2 -3 -7 9 -8 1 -7 5 5 -9 -10 6 -3 8 -1 -4 7 -5 4 4 1 5 6 10 8 10 0 4 6 -5 10 9 -3 6 4 -6 -8 1 -10 7 -6 3 4 -4 10 -6 -2 4 9 -7 -6 -2 -8 2 -8 10 6 8 4 7 2 10 0 1 2 2 2 8 3 9 0 3 0 5 -7 -5 9 8 7 3 4 -8 6 -2 4 6 3 4 5 -10 -9 -5 -8 -1 0 -6 -3 17 0 9 6 10 1 10 6 6 0 5 10 10 8 9 3 4 0 ...
output:
1.63741392 0.00000000 0.00000000 2.56572212 0.00000000 0.00000000 1.87681380 0.00000000 0.00000000 0.00000000 0.62560460 0.37536276 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.0...
result:
ok 100000 numbers
Test #11:
score: 0
Accepted
time: 94ms
memory: 3840kb
input:
10000 -7 -8 9 -1 5 5 6 -5 10 1 -5 9 -10 10 -1 -2 10 3 7 -8 -9 5 -7 -8 -1 5 2 5 0 2 8 10 6 8 0 4 -6 -3 10 1 -5 3 7 -10 -6 7 8 -1 7 4 8 -8 8 -4 6 8 6 2 7 1 8 8 1 -6 8 2 -4 3 1 -9 -9 7 -1 -6 7 4 2 -10 10 -5 6 4 1 8 1 6 7 9 3 6 9 9 2 10 8 10 1 2 0 -8 10 -10 -3 4 4 -4 -10 7 7 8 9 6 10 3 9 -8 0 8 -3 4 6 1...
output:
0.00000000 108.52193507 0.00000000 0.00000000 54.26096753 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 220.20000000 31.03053571 0.00000000 0.00000000 23.60489067 0.00000000 0.00000000 21.9371...
result:
ok 100000 numbers
Test #12:
score: 0
Accepted
time: 96ms
memory: 3968kb
input:
10000 -5 3 9 -4 -1 3 2 -1 2 8 -3 0 10 3 8 -5 -5 10 -8 6 5 8 0 1 4 10 8 9 5 10 5 10 4 4 0 1 0 7 1 2 6 8 6 3 2 -9 -9 -3 -7 -4 10 4 5 -9 9 -5 1 -1 -5 6 9 2 3 9 1 5 -2 0 9 8 0 4 2 -5 -10 8 -9 9 3 -2 9 5 8 -10 1 -9 -3 7 -7 2 3 1 3 13 4 6 6 8 3 10 4 6 1 2 4 5 6 10 2 6 1 3 4 9 2 3 0 9 8 8 -10 -8 8 -2 -10 4...
output:
0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 25.84693878 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0....
result:
ok 100000 numbers
Test #13:
score: -100
Wrong Answer
time: 83ms
memory: 4096kb
input:
3000 78 -37 984 -936 -370 9 158 -911 94 -338 -910 -20 -938 746 -972 922 -628 988 107 951 719 -94 936 -815 876 7 717 -960 -107 -231 -851 -112 -963 136 -970 979 99 565 655 -821 120 66 61 89 53 73 5 67 100 100 60 60 22 74 40 68 29 95 81 89 73 75 2 65 3 70 41 64 13 61 38 52 74 82 72 85 89 92 62 77 28 39...
output:
0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.0...
result:
wrong answer 9158th numbers differ - expected: '0.00000', found: '0.00016', error = '0.00016'