QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#381910#7734. Intersection over UnionmshcherbaWA 1249ms4044kbC++203.1kb2024-04-07 21:44:412024-04-07 21:44:47

Judging History

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

  • [2024-04-07 21:44:47]
  • 评测
  • 测评结果:WA
  • 用时:1249ms
  • 内存:4044kb
  • [2024-04-07 21:44:41]
  • 提交

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 * co + h * si < a * co * si ? 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, 60)
        {
            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, 60)
    {
        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: 1ms
memory: 4044kb

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
Wrong Answer
time: 1249ms
memory: 3908kb

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.49999999737417562
0.68523458057386941
0.45422482250722899
0.50028739390208503
0.98029611059210510
0.49196753894962870
0.54403738870671092
0.37278662355336414
0.92311833176433285
0.8925587008596665...

result:

wrong answer 9th numbers differ - expected: '0.4559617', found: '0.4542248', error = '0.0017369'