QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#381894 | #7734. Intersection over Union | mshcherba | TL | 0ms | 3872kb | C++20 | 3.1kb | 2024-04-07 21:30:59 | 2024-04-07 21:30:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long double db;
void solve()
{
vector<PII> v(4);
for (auto& [x, y] : v)
cin >> x >> y;
if (v[0].F == v[1].F || v[0].S == v[1].S)
{
cout << "1\n";
return;
}
db a, b, alpha, tg, ctg, si, co;
FOR(i, 0, 4)
{
auto [x1, y1] = v[i];
auto [x2, y2] = v[(i + 1) % 4];
if (x1 < x2 && y1 < y2)
{
auto [x3, y3] = v[(i + 2) % 4];
a = hypot(x3 - x2, y3 - y2);
b = hypot(x2 - x1, y2 - y1);
tg = (db)(y2 - y1) / (x2 - x1);
ctg = 1 / tg;
co = 1 / sqrt(tg * tg + 1);
si = 1 / sqrt(ctg * ctg + 1);
}
}
if (a * co > b * si)
{
swap(a, b);
swap(tg, ctg);
swap(co, si);
}
auto f1 = [&](db w, db h)
{
db inte = a * b - (tg + ctg) * (w * w + h * h);
db uni = a * b + (a * co - w * ctg - h) * (a * si - h * tg - w) + (b * co - h * ctg - w) * (b * si - w * tg - h);
return inte / uni;
};
auto f2 = [&](db w, db h)
{
db inte = a * b - (2 * a * w * co + 2 * a * h * si + w * w * tg + h * h * ctg - 2 * w * h - a * a * co * si);
db uni = a * b + (b * co - h * ctg - w) * (b * si - w * tg - h);
return inte / uni;
};
auto f = [&](db w, db h)
{
return w * ctg + h * tg < a ? f1(w, h) : f2(w, h);
};
const db c = (-1 + sqrt(5)) / 2;
auto g = [&](db w)
{
db l = 0, r = a * co;
db m1 = r - c * (r - l), fm1 = f(w, m1),
m2 = l + c * (r - l), fm2 = f(w, m2);
FOR(it, 0, 74)
{
if (fm1 > fm2)
{
r = m2;
m2 = m1;
fm2 = fm1;
m1 = r - c * (r - l);
fm1 = f(w, m1);
}
else
{
l = m1;
m1 = m2;
fm1 = fm2;
m2 = l + c * (r - l);
fm2 = f(w, m2);
}
}
return f(w, (l + r) / 2);
};
db l = 0, r = a * si;
db m1 = r - c * (r - l), gm1 = g(m1),
m2 = l + c * (r - l), gm2 = g(m2);
FOR(it, 0, 74)
{
if (gm1 > gm2)
{
r = m2;
m2 = m1;
gm2 = gm1;
m1 = r - c * (r - l);
gm1 = g(m1);
}
else
{
l = m1;
m1 = m2;
gm1 = gm2;
m2 = l + c * (r - l);
gm2 = g(m2);
}
}
cout << g((l + r) / 2) << "\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(17);
int t;
cin >> t;
while (t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3872kb
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.70710678118654752 1 0.62384322483109367
result:
ok 3 numbers
Test #2:
score: -100
Time Limit Exceeded
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.99296541252647005 0.99999993156883114 0.59086981567862606 0.62177048491080392 0.57883238413512738 1 0.49999999737417561 0.68523458057386941 0.45361597934600157 0.50028739390208503 0.98029611059210510 0.49196753831969629 0.54403738870671092 0.37278662355336632 0.92311833176433285 0.8925587008596665...