QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#372592#3035. GhostSolitaryDream#AC ✓2930ms16156kbC++174.3kb2024-03-31 16:03:132024-03-31 16:03:14

Judging History

你现在查看的是最新测评结果

  • [2024-03-31 16:03:14]
  • 评测
  • 测评结果:AC
  • 用时:2930ms
  • 内存:16156kb
  • [2024-03-31 16:03:13]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define double long double
const int N = 2e6 + 10;
typedef pair<double, double> pdd;
pdd operator+(pdd a, pdd b) {
    return pdd(a.first + b.first, a.second + b.second);
}
struct Line {
    double k, c;
};
struct Convex {
    vector<Line> line;
    vector<double> cross;
    void Push(double k, double c) {
        line.push_back({k, c});
    }
    inline double CrossX(Line a, Line b) {
        return -(a.c - b.c) / (a.k - b.k); 
    }
    inline bool Check(Line a, Line b, Line c) {
        // return -(b.c - a.c) / (b.k - a.k) <= -(c.c - a.c) / (c.k - a.k);
        long long X1 = -(b.c - a.c);
        long long Y1 = (b.k - a.k);
        long long X2 = -(c.c - a.c);
        long long Y2 = (c.k - a.k);
        int rst = X1 * Y2 <= X2 * Y1;
        if (Y1 < 0) rst ^= 1;
        if (Y2 < 0) rst ^= 1;
        return rst;
    }
    void Solve(vector<double> &sp) {
        sort(line.begin(), line.end(), [](Line a, Line b) {
            if (a.k == b.k) return a.c > b.c;
            return a.k > b.k;
        });
        int top = 0;
        for (int i = 1; i < line.size(); ++i) {
            while (top >= 0) {
                if (line[i].k == line[top].k) {
                    --top;
                } else if (top >= 1 && Check(line[top - 1], line[i], line[top])) {
                    --top;
                } else break;
            }
            line[++top] = line[i];
        }
        line.resize(top + 1);
        cross.resize(line.size() - 1);
        for (int i = 0; i < cross.size(); ++i) cross[i] = CrossX(line[i], line[i + 1]);
        for (auto x : cross) if (x > 0) sp.push_back(x);
    }
    pdd Get(double x) {
        int p = lower_bound(cross.begin(), cross.end(), x) - cross.begin();
        return {line[p].k, line[p].c};
    }
    void Clear() {
        line.clear();
        cross.clear();
    }
} U, D, R, L;
vector<pair<double, double>> A;
namespace Seg {
    double f[N];
    int D;
    inline void Init() {
        D = A.size() + 2;
        for (int i = 0; i < A.size(); ++i) {
            f[D + i] = A[i].second;
        }
        for (int i = D - 1; i; --i) f[i] = max(f[i << 1], f[i << 1 | 1]);
    }
    inline double Ask(int x, int y) {
        if (x > y) return 0;
        double ans = 0;
        for (int l = D + x - 1, r = D + y + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
            if (~l & 1) ans = max(ans, f[l ^ 1]);
            if ( r & 1) ans = max(ans, f[r ^ 1]);
        }
        return ans;
    }
}
inline double GetArea(double x) {
    auto [k1, c1] = U.Get(x) + D.Get(x);
    auto [k2, c2] = R.Get(x) + L.Get(x);
    return max<double>(k1 * x + c1, 0.) * max<double>(k2 * x + c2, 0.);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed << setprecision(15);
    int Case;
    cin >> Case;
    while (Case--) {
        L.Clear(); R.Clear();
        U.Clear(); D.Clear();
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            int x, y, u, v, dx, dy;
            cin >> x >> y >> u >> v >> dx >> dy;
            U.Push(dy, v); D.Push(-dy, -y);
            R.Push(dx, u); L.Push(-dx, -x); 
        }
        vector<double> sp;
        sp.push_back(1e6);
        U.Solve(sp); D.Solve(sp);
        R.Solve(sp); L.Solve(sp);
        sort(sp.begin(), sp.end());
        sp.erase(unique(sp.begin(), sp.end()), sp.end());
        double last = 0;
        A.clear();
        A.push_back({0, GetArea(0)});
        for (auto cur : sp) {
            double mid = (last + cur) * 0.5;
            auto [k1, c1] = U.Get(mid) + D.Get(mid);
            auto [k2, c2] = R.Get(mid) + L.Get(mid);
            double x = -(k1 * c2 + k2 * c1) * 0.5 / (k1 * k2);
            if (x >= last && x <= cur) A.push_back({x, GetArea(x)});
            A.push_back({cur, GetArea(cur)});
            last = cur;
        }
        Seg::Init();
        int m;
        cin >> m;
        for (int i = 1; i <= m; ++i) {
            double x, y;
            cin >> x >> y;
            double ans = max(GetArea(x), GetArea(y));
            int p1 = lower_bound(A.begin(), A.end(), pdd(x, 0)) - A.begin();
            int p2 = lower_bound(A.begin(), A.end(), pdd(y, 0)) - A.begin() - 1;
            ans = max(ans, Seg::Ask(p1, p2));
            cout << ans << '\n';
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 940ms
memory: 4088kb

input:

4000
2
-5 -5 3 1 1 -5
-3 -4 -1 2 -2 1
169
4.5924 9.7635
4.9674 5.3219
8.2418 9.6649
6.5743 8.6108
5.3524 6.4199
2.1932 4.3636
1.7115 6.6926
0.5762 4.0628
5.0348 7.5678
6.2170 6.3381
7.1571 8.0276
1.7285 2.3730
0.3843 2.9644
0.0038 0.3971
3.8448 9.7040
4.0458 9.4878
1.6425 7.9132
8.9195 9.4455
4.2563...

output:

0.000000000000000
0.000000000000000
0.000000000000000
0.000000000000000
0.000000000000000
0.000000000000000
0.000000000000000
3.085600000000000
0.000000000000000
0.000000000000000
0.000000000000000
0.000000000000000
5.388400000000000
9.954400000000000
0.000000000000000
0.000000000000000
0.0000000000...

result:

ok OK!

Test #2:

score: 0
Accepted
time: 2930ms
memory: 9420kb

input:

49
20119
453553 453553 999314 999117 128392 128392
625880 625880 999937 999372 -124296 -124296
-34395 -34395 999431 999379 617841 617841
773531 773531 999210 999826 -458742 -458742
-351946 -351946 999501 999848 827822 827822
751364 751364 999088 999855 -391959 -391959
698502 698502 999908 999195 -26...

output:

28458932215.126596050336957
26610127672.555073169991374
28532937150.676446726545691
28532937150.676446726545691
28232156121.935278080403805
28014514974.478361969813704
26633365234.957375001162291
28014514974.478361969813704
28532937150.676446726545691
27190169607.005666369572282
26644935633.67628928...

result:

ok OK!

Test #3:

score: 0
Accepted
time: 1466ms
memory: 16156kb

input:

11
2437
-319663 -890371 927261 655392 1 3
-257629 -963537 454576 973758 5 -6
-143353 -761004 767384 895313 1 -4
-474255 -62583 604311 925105 -5 -7
-129789 -629223 875141 641849 3 6
-54357 -600036 845387 199014 2 3
-946287 -251448 306995 217922 7 -3
-480329 -265842 271418 189372 5 -4
-352502 -775709 ...

output:

64584.375000000000000
64584.375000000000000
64584.375000000000000
56289.635964240000000
37538.986472639999999
64584.375000000000000
64584.375000000000000
64584.375000000000000
64584.375000000000000
47531.486884560000004
63419.838128639999997
49064.913896639999997
20520.108799439999999
64584.37500000...

result:

ok OK!