QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#884380#9547. Two Convex HolesUESTC_NLNSWA 98ms4096kbC++206.0kb2025-02-06 02:10:592025-02-06 02:10:59

Judging History

This is the latest submission verdict.

  • [2025-02-06 02:10:59]
  • Judged
  • Verdict: WA
  • Time: 98ms
  • Memory: 4096kb
  • [2025-02-06 02:10:59]
  • Submitted

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 = sqrtl(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;
        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 == 32747) {
        //     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, (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
-8 -3 10 -4 3
5 2
-9 5
-8 3
4 -2
7 8
-3 7
4 3
-7 0
5 -10
9 1
3 1
3
1 9
6 6
6 8
*/

详细

Test #1:

score: 100
Accepted
time: 1ms
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: 4096kb

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.01768760

result:

ok found '910.01769', expected '910.01769', error '0.00000'

Test #3:

score: 0
Accepted
time: 97ms
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: 98ms
memory: 3968kb

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: 3840kb

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: 98ms
memory: 3712kb

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: 97ms
memory: 3968kb

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: 96ms
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: 97ms
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: 98ms
memory: 3968kb

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: 97ms
memory: 4096kb

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: 98ms
memory: 4096kb

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 10156th numbers differ - expected: '0.00000', found: '0.00011', error = '0.00011'