QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#497365#7734. Intersection over UnionlonelywolfAC ✓522ms3972kbC++232.7kb2024-07-29 02:59:282024-07-29 02:59:28

Judging History

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

  • [2024-07-29 02:59:28]
  • 评测
  • 测评结果:AC
  • 用时:522ms
  • 内存:3972kb
  • [2024-07-29 02:59:28]
  • 提交

answer

#include<bits/stdc++.h>
using ll = long long;
const int N = 1005;
using std::cin, std::cout;
using db = long double;
struct vec2 {
    db x, y;
    db norm() const {
        return x * x + y * y;
    }
};
vec2 operator + (vec2 x, vec2 y) { return {x.x + y.x, x.y + y.y}; }
vec2 operator - (vec2 x, vec2 y) { return {x.x - y.x, x.y - y.y}; }
vec2 operator * (vec2 x, db y) { return {x.x * y, x.y * y}; }
vec2 r90(vec2 x) { return {-x.y, x.x}; }
db operator * (vec2 x, vec2 y) { return x.x * y.y - x.y * y.x; }
db operator % (vec2 x, vec2 y) { return x.x * y.x + x.y * y.y; }
vec2 get() {
    int x, y; cin >> x >> y;
    return {(db)x,db(y)};
}
const db eps = 1e-12;
struct func {
    vec2 o;
    db c;
    db prod;
    bool init(vec2 a, vec2 b) {
        o = r90(a - b);
        if(o.x < 0) a.x *= -1, b.x *= -1, std::swap(a, b);
        if(o.y < 0) a.y *= -1, b.y *= -1, std::swap(a, b);
        o = r90(a - b);
        if(fabs(o.x) < eps) return 0;
        if(fabs(o.y) < eps) return 0;
        o = o * (1 / sqrt(o.norm()));
        c = o % a;
        prod = o.norm() / o.x / o.y;
        return 1;
    }
    db calc(db x, db y) const {
        db v = std::max<db>(0, x * o.x + y * o. y - c);
        return v * v * prod;
    }
} pb, fsy;
db f(db x, db y) {
    return pb.calc(x, y) + fsy.calc(x, y);
}
db S;
db g(db x, db y) {
    db r = f(x, y);
    return (4 * x * y - r) / (S + r);
}
db ly, ry;
db findmax(db a, db c, auto f) {
    auto g = [&](db l, db r) {
        return l + (r - l) * (std::numbers::phi_v<db> - 1);
    };
    db b = g(a, c), bv = f(b);
    for(int i = 0;i < 45;++i) {
        db x = g(a, b), xv = f(x);
        if(xv > bv) {
            c = b, b = x, bv = xv;
        } else {
            a = c, c = x;
        }
    }
    return bv;
}
int main() {
    std::ios::sync_with_stdio(false), cin.tie(0);
    int T; cin >> T;
    for(int i = 0;i < T;++i) {
        vec2 a[4];
        vec2 s = {};
        for(auto & x : a) x = get(), s = s + x;
        if((a[1] - a[0]) * (a[2] - a[0]) < 0) {
            std::reverse(a, a + 4);
        }
        s = s * 0.25;
        for(auto & x : a) x = x - s, x = x * (1 / sqrt(x.norm()));
        S = (a[1] - a[0]) * (a[2] - a[0]);
        if(!pb.init(a[0], a[1])) {
            puts("1");
            continue;
        }
        if(!fsy.init(a[1], a[2])) {
            puts("1");
            continue;
        }
        db l = 0, r = a[0].x;
        ry = a[0].y;
        for(auto & x : a) {
            r = std::max(r, x.x);
            ry = std::max(ry, x.y);
        }
        printf("%.12Lf\n", findmax(l, r, [&](db x) { return findmax(0, ry, [&](db y) { return g(x, y); });}));
    }

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0 2 2 0 0 -2 -2 0
7 -2 9 -2 9 2 7 2
7 13 11 10 5 2 1 5

output:

0.707106781187
1
0.623843224831

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 514ms
memory: 3920kb

input:

10000
-568767734 379152673 -565681345 -54946093 -131582579 -51859704 -134668968 382239062
-194884120 -559906233 -194884142 -158042604 -998611400 -158042648 -998611378 -559906277
459335966 -945199065 478030260 -934243779 450535683 -887326546 431841389 -898281832
-483567491 491964356 -523827401 408140...

output:

0.992965412526
0.999999931569
0.590869815679
0.621770484911
0.578832384135
1
0.499999997374
0.685234580574
0.455961719767
0.500287393902
0.980296110592
0.492043571792
0.544037388707
0.380480107105
0.923118331764
0.892558700860
0.617680319575
0.945676970215
0.499874372003
0.999954387824
0.64742147647...

result:

ok 10000 numbers

Test #3:

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

input:

11
-999999999 238255972 -999999998 238255969 1000000000 904922635 999999999 904922638
678595699 247253438 -168427985 235963055 -168327599 228431927 678696085 239722310
-192017652 -554548342 868151340 -554547158 868151544 -737211410 -192017448 -737212594
-999841167 -113051212 -112620642 -999956242 99...

output:

0.000035355964
0.500220885906
0.999996662877
0.696307888858
0.000031623277
0.282517709967
0.991221032540
0.164529210010
0.058187402409
0.138257593876
0.047444732176

result:

ok 11 numbers

Test #4:

score: 0
Accepted
time: 499ms
memory: 3920kb

input:

10000
-948990367 928227410 -873396995 996000778 851933079 -928405843 776339707 -996179211
-109521044 -738814438 897130737 -601388427 761521924 391952296 -245129857 254526285
534464734 -606222047 863618110 -14372639 -542024234 767366629 -871177610 175517221
636708790 -567653754 157968528 -562763908 1...

output:

0.150788535447
0.888031200760
0.612622357967
0.982425366044
0.668476523470
0.999978015364
0.465324061047
1
0.959119697955
0.757335362026
0.697246932189
0.292591505483
0.038463046524
0.918212709857
0.933584756018
0.705784762621
0.713008366420
0.859067589759
0.103119241299
0.501046754828
0.73890044096...

result:

ok 10000 numbers

Test #5:

score: 0
Accepted
time: 522ms
memory: 3880kb

input:

10000
0 1 1 0 4 3 3 4
0 1 3 0 8 15 5 16
0 5 25 0 64 195 39 200
0 7 49 0 124 525 75 532
0 8 4 0 34 15 30 23
0 8 12 0 38 39 26 47
0 40 100 0 274 435 174 475
0 56 196 0 514 1113 318 1169
0 32 8 0 212 51 204 83
0 32 24 0 124 75 100 107
0 160 200 0 692 615 492 775
0 224 392 0 1172 1365 780 1589
0 1081897...

output:

0.500000000000
0.500000000000
0.500000000000
0.500000000000
0.500000000000
0.500000000000
0.500000000000
0.500000000000
0.500000000000
0.500000000000
0.500000000000
0.500000000000
0.499980612136
0.508975979477
0.502482809599
0.499999976773
0.499979707128
0.500872674554
0.500000000000
0.500009114916
...

result:

ok 10000 numbers

Test #6:

score: 0
Accepted
time: 509ms
memory: 3972kb

input:

10000
0 1 1 0 2 1 1 2
-1000000000 -999999999 -999999999 -1000000000 1000000000 999999999 999999999 1000000000
-1000000000 -999999999 999999999 -1000000000 1000000000 999999999 -999999999 1000000000
-1000000000 0 0 -1000000000 1000000000 0 0 1000000000
0 1 1 0 1000000000 999999999 999999999 100000000...

output:

0.707106781187
0.000015811513
0.999999999478
0.707106781187
0.000022360930
0.999999998999
0.999122691590
0.098501781353
0.084419491744
0.992172576298
0.710505324788
0.999999975547
0.000777229084
0.008526256853
0.133476599451
0.001576838539
0.006882029766
0.000400107263
0.999701779478
0.709221283499
...

result:

ok 10000 numbers

Test #7:

score: 0
Accepted
time: 516ms
memory: 3792kb

input:

10000
0 508076 762114 0 762124 15 10 508091
-998442427 -981568404 -498442427 -981568405 -498442425 18431595 -998442425 18431596
0 1 250000000 0 250000001 250000000 1 250000001
-999999999 -27628659 -999999998 -27628661 1000000000 972371338 999999999 972371340
-999999999 238255972 -999999998 238255969...

output:

0.003270474224
0.999999997499
0.999999996000
0.000025000313
0.000035355964
0.000046098785
0.000068009665
0.000101247409
0.000145784423
0.000212743101
0.000313298169
0.000469817684
0.000704698317
0.001051563894
0.001577710694
0.002361862599
0.003539251929
0.005313553995
0.007980888180
0.011989483444
...

result:

ok 10000 numbers

Extra Test:

score: 0
Extra Test Passed