QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#363454#8505. Almost AlignedDays_of_Future_Past#WA 656ms69840kbC++233.6kb2024-03-23 22:47:032024-03-23 22:47:05

Judging History

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

  • [2024-03-23 22:47:05]
  • 评测
  • 测评结果:WA
  • 用时:656ms
  • 内存:69840kb
  • [2024-03-23 22:47:03]
  • 提交

answer

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
typedef long long LL;
typedef unsigned long long ULL;
#define all(x) ((x).begin()), ((x).end())
#define pb push_back
typedef double D;
struct P {
    D x, y;
    void print() const{
        printf("%.6f %.6f\n", x, y);
    }
    P operator + (const P & b) const { return P{x + b.x, y + b.y}; }
    P operator - (const P & b) const { return P{x - b.x, y - b.y}; }
    D operator * (const P & b) const {
        return x * b.y - y * b.x;
    }
};
P operator * (const D & x, const P & b) { return P{x * b.x, x * b.y}; }
struct L {
    P s, d;
    bool contains(const P & x) {
        return d * (x - s) > 0;
    }
};
P intersect(const L & a, const L & b) {
    D lambda = (b.s - a.s) * b.d / (a.d * b.d);
    return a.s + lambda * a.d;
}
vector<P> uh[2], lh[2];
vector<P> compute_uh(vector<L> & lines) {
    sort(lines.begin(), lines.end(), [&](const L & a, const L & b) {
        return a.d.y < b.d.y || a.d.y == b.d.y && a.s.x < b.s.x;
    });
    vector<L> res;
    res.pb(L{P{0, 0}, P{0, -1}});
    for(int i = 0, j; i < (int)lines.size(); i = j) {
        for(j = i; j < (int)lines.size() && lines[i].d.y == lines[j].d.y; j++);
        L & l(lines[j - 1]);
        while(res.size() >= 2) {
            P i = intersect(res.back(), res[res.size() - 2]);
            if(!l.contains(i)) {
                res.pop_back();
            } else {
                break;
            }
        }
        res.pb(l);
    }
    vector<P> uh;
    for(int i = 0; i + 1 < (int)res.size(); i++) {
        uh.pb(intersect(res[i], res[i + 1]));
    }
    uh.pb(intersect(res.back(), L{P{1e10, 1e10}, P{0, -1}}));
    return uh;
}
D gety(const P & a, const P & b, const D & x) {
    return a.y + (b.y - a.y) * (x - a.x) / (b.x - a.x);
}
const int N = 1000011;
int x[N][2], vx[N][2];
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d%d%d%d", &x[i][0], &x[i][1], &vx[i][0], &vx[i][1]);
    }
    for(int d = 0; d < 2; d++) {
        vector<L> lines;
        for(int i = 0; i < n; i++) {
            lines.push_back(L{P{0, x[i][d]}, P{1, vx[i][d]}});
        }
        uh[d] = compute_uh(lines);
        for(int i = 0; i < n; i++) {
            lines[i] = L{P{0, -x[i][d]}, P{1, -vx[i][d]}};
        }
        lh[d] = compute_uh(lines);
        for(auto & p : lh[d]) {
            p.y = -p.y;
        }
        /*printf("uh[%d] : \n", d);
        for(auto & p : uh[d]) {
            p.print();
        }
        printf("lh[%d] : \n", d);
        for(auto & p : lh[d]) {
            p.print();
        }*/
    }
    D ans = 1e50;
    auto update = [&](const D & x) {
        D u[2], d[2];
        D res = 1;
        for(int d = 0; d < 2; d++) {
            int p = lower_bound(uh[d].begin(), uh[d].end(), P{x, 0}, [&](const P & a, const P & b) {return a.x < b.x;}) - uh[d].begin();
            p = min(p, (int)uh[d].size() - 1);
            p = max(p, 1);
            D u = gety(uh[d][p - 1], uh[d][p], x);
            p = lower_bound(lh[d].begin(), lh[d].end(), P{x, 0}, [&](const P & a, const P & b) {return a.x < b.x;}) - lh[d].begin();
            p = min(p, (int)lh[d].size() - 1);
            p = max(p, 1);
            D l = gety(lh[d][p - 1], lh[d][p], x);
            res *= u - l;
        }
        ans = min(ans, res);
    };
    for(int d = 0; d < 2; d++) {
        for(auto & p : uh[d]) {
            update(p.x);
        }
        for(auto & p : lh[d]) {
            update(p.x);
        }
    }
    printf("%.12f\n", ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 6148kb

input:

4
0 0 10 10
0 0 10 10
10 10 -10 -10
10 0 -20 0

output:

22.222222222222

result:

ok found '22.222222222', expected '22.222222222', error '0.000000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5972kb

input:

3
0 -1 0 2
1 1 1 1
-1 1 -1 1

output:

0.000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #3:

score: 0
Accepted
time: 1ms
memory: 5864kb

input:

3
0 -1 0 -2
1 1 1 1
-1 1 -1 1

output:

4.000000000000

result:

ok found '4.000000000', expected '4.000000000', error '0.000000000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 5972kb

input:

1
0 0 0 0

output:

0.000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 5828kb

input:

4
1000000 1000000 -1 -1000000
1000000 -1000000 -1000000 1
-1000000 -1000000 1 1000000
-1000000 1000000 1000000 -1

output:

3999984000032.000000000000

result:

ok found '3999984000032.000000000', expected '3999984000032.000000000', error '0.000000000'

Test #6:

score: -100
Wrong Answer
time: 656ms
memory: 69840kb

input:

1000000
-871226 486657 -467526 31395
-65837 846554 469710 -907814
927993 -45099 713462 -276539
261942 483255 746021 811070
63449 -779486 588838 -413687
812070 -87868 -813499 -420768
112521 -622607 -832012 921368
-182120 517379 -401743 -837524
-685985 337832 643014 135144
12895 326935 -495720 930620
...

output:

3999988000008.000000000000

result:

wrong answer 1st numbers differ - expected: '3999996000000.0000000', found: '3999988000008.0000000', error = '0.0000020'