Submission #69871435

---

Source Code Expand

#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 0
#endif
using namespace std;
using ll = long long;
using db = double;
const ll N = 1e6 + 5;
const ll md = 998244353;
const ll MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db eps = 1e-6;
const db E = 2.718281828459045;
typedef pair<ll, ll> PLL;
#define fi first
#define se second
db sx1, sx2, sy1, sy2, ex1, ex2, ey1, ey2;
db a1, b1, a2, b2, c1, d1, c2, d2;
db dis(db x1, db y1, db x2, db y2)
{
    db res = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    return res;
}
db z1, z2;
db cal(db t)
{
    if (t < 0)
        return 1e9;
    sx1 = a1, sy1 = b1, ex1 = c1, ey1 = d1;
    sx2 = a2, sy2 = b2, ex2 = c2, ey2 = d2;
    db xx1 = (ex1 - sx1);
    db yy1 = (ey1 - sy1);
    db xx2 = (ex2 - sx2);
    db yy2 = (ey2 - sy2);
    db res1 = sqrtl(dis(sx1, sy1, ex1, ey1));
    db res2 = sqrtl(dis(sx2, sy2, ex2, ey2));
    z1 = min(res1, res2), z2 = max(res1, res2);
    if (t > min(res1, res2))
        return 1e9;
    sx1 += xx1 / res1 * t;
    sy1 += yy1 / res1 * t;
    sx2 += xx2 / res2 * t;
    sy2 += yy2 / res2 * t;
    // cout << sx1 << ' ' << sy1 << '\n';
    if (t > res1)
        sx1 = ex1, sy1 = ey1;
    if (t > res2)
        sx2 = ex2, sy2 = ey2;
    return dis(sx1, sy1, sx2, sy2);
}
db cal2(db t)
{
    sx1 = a1, sy1 = b1, ex1 = c1, ey1 = d1;
    sx2 = a2, sy2 = b2, ex2 = c2, ey2 = d2;
    db xx1 = (ex1 - sx1);
    db yy1 = (ey1 - sy1);
    db xx2 = (ex2 - sx2);
    db yy2 = (ey2 - sy2);
    db res1 = sqrtl(dis(sx1, sy1, ex1, ey1));
    db res2 = sqrtl(dis(sx2, sy2, ex2, ey2));
    sx1 += xx1 / res1 * t;
    sy1 += yy1 / res1 * t;
    sx2 += xx2 / res2 * t;
    sy2 += yy2 / res2 * t;
    // cout << sx1 << ' ' << sy1 << '\n';
    if (t > res1)
        sx1 = ex1, sy1 = ey1;
    if (t > res2)
        sx2 = ex2, sy2 = ey2;
    return dis(sx1, sy1, sx2, sy2);
}
void solve()
{
    cin >> a1 >> b1 >> c1 >> d1;
    cin >> a2 >> b2 >> c2 >> d2;
    db l = 0, r = 1e9;
    for (int i = 0; i < 300; i++)
    {
        db lmid = l + (r - l) / 3;
        db rmid = r - (r - l) / 3;
        if (cal(rmid) >= cal(lmid))
            r = rmid;
        else
            l = lmid;
    }
    db ans = sqrtl(cal(l));
    l = z1, r = z2;
    for (int i = 0; i < 300; i++)
    {
        db lmid = l + (r - l) / 3;
        db rmid = r - (r - l) / 3;
        if (cal2(rmid) >= cal2(lmid))
            r = rmid;
        else
            l = lmid;
    }
    db res = sqrtl(cal2(l));
    ans = min(ans, res);
    cout << fixed << setprecision(15) << ans << '\n';
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
}

Submission Info

Judge Result