QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#884395 | #9547. Two Convex Holes | UESTC_NLNS | WA | 0ms | 3968kb | C++20 | 5.0kb | 2025-02-06 02:45:41 | 2025-02-06 02:45:42 |
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 t;
const ldb eps = 1e-12;
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);
for (auto& u : c1) u = rotate((u - a0) * alp1, v);
for (auto& u : c2) u = rotate((u - a0) * alp2, v);
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);
int i = 0,j =0;
while(i<s.size() && s[i].a.y<lst_z)i++;
while(j<t.size() && t[j].a.y<lst_z)j++;
for (; i < s.size() && j < t.size();) {
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});
}
ans.back().a1 = ans.back().a2 = ans.back().a3 = 0;
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;
return a1 + a2 * t + a3 * t * t / 2;
};
int cq;
cin >> cq;
for (int i = 0; i < cq; ++i) {
ldb t1, t2;
cin >> t1 >> t2;
ldb result = t1 == t2 ? query2(t1) : (query(t2) - query(t1)) / (t2 - t1);
printf("%.8LF\n", result * beta);
}
}
int main() {
cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
cin >> t;
while (t--) solve();
}
详细
Test #1:
score: 0
Wrong Answer
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.00000000 0.00000000 0.00000000
result:
wrong answer 1st numbers differ - expected: '0.45000', found: '0.00000', error = '0.45000'