QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#332768 | #7734. Intersection over Union | ucup-team1209 | AC ✓ | 339ms | 3968kb | C++20 | 2.3kb | 2024-02-19 15:59:09 | 2024-02-19 15:59:09 |
Judging History
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 < 50;++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: 3820kb
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: 326ms
memory: 3968kb
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: 3896kb
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: 317ms
memory: 3896kb
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: 332ms
memory: 3940kb
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: 314ms
memory: 3836kb
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.999999999500 0.707106781187 0.000022360930 0.999999999000 0.999122691590 0.098501781353 0.084419491744 0.992172576298 0.710505324788 0.999999975548 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: 339ms
memory: 3896kb
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.999999997500 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