QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#376272#7734. Intersection over UnionmshcherbaWA 1322ms3904kbC++203.0kb2024-04-04 00:49:302024-04-04 00:49:31

Judging History

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

  • [2024-04-04 00:49:31]
  • 评测
  • 测评结果:WA
  • 用时:1322ms
  • 内存:3904kb
  • [2024-04-04 00:49:30]
  • 提交

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 double db;

const db EPS = 1e-9;

struct Pt
{
	db x, y;
	Pt operator-(const Pt& p) const
	{
		return {x - p.x, y - p.y};
	}
};
int sgn(db x)
{
	return (EPS < x) - (x < -EPS);
}
Pt perp(const Pt& p)
{
	return {-p.y, p.x};
}
db cross(const Pt& p, const Pt& q)
{
	return p.x * q.y - p.y * q.x;
}
db orient(const Pt& p, const Pt& q, const Pt& r)
{
	return cross(q - p, r - p);
}
ostream& operator<<(ostream& os, const Pt& p)
{
    return os << "(" << p.x << "," << p.y << ")";
}

void solve()
{
    vector<Pt> v(4);
    for (Pt& p : v)
        cin >> p.x >> p.y;
    if (v[0].x == v[1].x || v[0].y == v[1].y)
    {
        cout << "1\n";
        return;
    }
    if (sgn(orient(v[0], v[1], v[2])) < 0)
        reverse(ALL(v));
    int indexMin = 0;
    FOR(i, 1, 4)
    {
        if (v[i].x < v[indexMin].x)
        {
            indexMin = i;
        }
    }
    vector<Pt> nv;
    FOR(i, indexMin, indexMin + 4)
    {
        nv.PB(v[i % 4]);
    }
    v = nv;
    vector<db> xs, ys;
    for (const Pt& p: v)
    {
        xs.PB(p.x);
        ys.PB(p.y);
    }
    sort(ALL(xs));
    sort(ALL(ys));
    db area = cross(v[1] - v[0], v[3] - v[0]);
    db cx = (v[0].x + v[2].x) / 2, cy = (v[0].y + v[2].y) / 2;
    vector<Pt> u;
    auto g = [&](const Pt& p, const Pt& q, const Pt& r, const Pt& s) -> pair<db, db>
    {
        db ye = (s.x - p.x) / (r.x - p.x) * (r.y - p.y) + p.y;
        db yf = (s.x - p.x) / (q.x - p.x) * (q.y - p.y) + p.y;
        db xg = (s.y - p.y) / (q.y - p.y) * (q.x - p.x) + p.x;
        return {(ye - yf) * (s.x - p.x), (yf - s.y) * (xg - s.x)};
    };
    auto fxy = [&](db x, db y)
    {
        u = {{x, y}, {2 * cx - x, y}, {2 * cx - x, 2 * cy - y}, {x, 2 * cy - y}};
        auto [a1, b1] = g(v[0], v[1], v[3], u[0]);
        auto [a2, b2] = g(perp(v[3]), perp(v[0]), perp(v[2]), perp(u[3]));
        return (area - a1 - a2) / (area + b1 + b2);
    };
    auto fx = [&](db x)
    {
        db l = ys[0], r = ys[1];
        FOR(it, 0, 40)
        {
            db m1 = l + (r - l) * 0.4, m2 = r - (r - l) * 0.4;
            if (fxy(x, m1) < fxy(x, m2))
                l = m1;
            else
                r = m2;
        }
        return fxy(x, (l + r) / 2);
    };
    db l = xs[0], r = xs[1];
    FOR(it, 0, 40)
    {
        db m1 = l + (r - l) * 0.4, m2 = r - (r - l) * 0.4;
        if (fx(m1) < fx(m2))
            l = m1;
        else
            r = m2;
    }
    cout << fx((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: 3800kb

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.70710678118654757
1
0.62384322483109333

result:

ok 3 numbers

Test #2:

score: -100
Wrong Answer
time: 1322ms
memory: 3904kb

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.99296541252646986
0.99999993156883094
0.59086981567862573
0.62177048491080389
0.57883238413512716
1
0.49999999737417555
0.68523458057087439
0.45361597934666475
0.50028739390208499
0.98029611059210486
0.49196753831971057
0.54403738870671081
0.36331124813919580
0.92311833176381120
0.8925587008596703...

result:

wrong answer 9th numbers differ - expected: '0.4559617', found: '0.4536160', error = '0.0023457'