QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#121773#851. (Almost) Fair Cake-Cuttingkaruna#AC ✓3ms3780kbC++175.0kb2023-07-08 20:28:572023-07-08 20:28:59

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-08 20:28:59]
  • Judged
  • Verdict: AC
  • Time: 3ms
  • Memory: 3780kb
  • [2023-07-08 20:28:57]
  • Submitted

answer

#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

struct point {
    double x, y;
};

point operator-(point a, point b) {
    return {a.x - b.x, a.y - b.y};
}
double operator/(point a, point b) {
    return a.x * b.y - a.y * b.x;
}
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    int t; cin >> t;
    while (t--) {
        int n, m; cin >> n >> m;
        vector<array<int, 3>> p(n);
        for (auto &[x, y, z] : p) cin >> x >> y >> z;

        if (n >= 3) {
            cout << "100.000000%\n";
            continue;
        }
        else {
            vector<pair<point, int>> pt;
            pt.push_back({point{0, 0}, 0});
            pt.push_back({point{(double)m, 0}, 0});
            pt.push_back({point{(double)m, (double)m}, 0});
            pt.push_back({point{0, (double)m}, 0});

            bool flag = false;
            for (int i = 0; i < p.size(); i++) {
                auto [a, b, c] = p[i];

                double x;
                double y;

                int cnt = 0;
                if (b != 0) {
                    x = 0; y = -c / (double)b;
                    if (0 <= y && y <= m) pt.push_back({point{x, y}, i + 1}), ++cnt;

                    x = m; y = (-c - a * m) / (double)b;
                    if (0 <= y && y <= m) pt.push_back({point{x, y}, i + 1}), ++cnt;
                }
                if (a != 0) {
                    y = 0; x = -c / (double)a;
                    if (0 < x && x < m) pt.push_back({point{x, y}, i + 1}), ++cnt;

                    y = m; x = (-c - b * m) / (double)a;
                    if (0 < x && x < m) pt.push_back({point{x, y}, i + 1}), ++cnt;
                }
                if (cnt != 2) {
                    flag = true;
                    cout << "100.000000%\n";
                    break;
                }
            }
            if (flag) continue;

            auto f = [&](double x, double y) {
                if (y == 0) return x;
                else if (x == m) return m + y;
                else if (y == m) return 3 * m - x;
                else return 4 * m - y;
            };

            if (n == 2) {
                auto [a1, b1, c1] = p[0];
                auto [a2, b2, c2] = p[1];

                if (a1 * b2 - a2 * b1 == 0) {
                    cout << "100.000000%\n";
                    continue;
                }
                double x = (c2 * b1 - c1 * b2) / (double)(a1 * b2 - b1 * a2);
                double y = (c2 * a1 - c1 * a2) / (double)(b1 * a2 - a1 * b2);

                if (!(0 < x && x < m && 0 < y && y < m)) {
                    cout << "100.000000%\n";
                    continue;
                }

                sort(pt.begin(), pt.end(), [&](auto p, auto q) {
                    return f(p.first.x, p.first.y) < f(q.first.x, q.first.y);
                });

                point origin = {x, y};

                // for (int i = 0; i < 8; i++) {
                //     auto [x, y] = pt[i].first;
                //     cout << x << ' '<< y << endl;
                // }
                // cout << origin.x << ' ' << origin.y << '\n';

                double ans = 1e9;
                for (int i = 0; i < 8; i++) {
                    if (pt[i].second == 0) continue;

                    double area = 0;
                    for (int j = 0; j < 8; j++) {
                        point s = pt[(i + j) % 8].first;
                        point t = pt[(i + j + 1) % 8].first;

                        area += (s - origin) / (t - origin) * 0.5;
                        if (pt[(i + j + 1) % 8].second != 0) break;
                    }
                    ans = min(ans, area);
                }
                ans = (double)m * m - ans;
                ans /= (double)m * m;
                ans = ans * 100;

                cout.precision(6);
                cout << fixed << ans << "%\n";
            }
            else {
                sort(pt.begin(), pt.end(), [&](auto p, auto q) {
                    return f(p.first.x, p.first.y) < f(q.first.x, q.first.y);
                });

                double ans = 1e9;
                for (int i = 0; i < 6; i++) {
                    if (pt[i].second == 0) continue;

                    point origin = pt[i].first;
                    double area = 0;
                    for (int j = 1; j < 6; j++) {
                        point s = pt[(i + j) % 6].first;
                        point t = pt[(i + j + 1) % 6].first;

                        area += (s - origin) / (t - origin) * 0.5;
                        if (pt[(i + j + 1) % 6].second != 0) break;
                    }
                    ans = min(ans, area);
                }
                ans = (double)m * m -ans;
                ans /= (double)m * m;
                ans = ans * 100;

                cout.precision(6);
                cout << fixed << ans << "%\n";
            }
        }
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3744kb

input:

1
2 1000
0 1 -750
1 0 -750

output:

93.750000%

result:

ok OK!

Test #2:

score: 0
Accepted
time: 1ms
memory: 3780kb

input:

500
1 1000
1 0 -300
1 1000
1 1 -500
1 1000
1 1 -1000
1 2
0 -1 1
1 1
-1 -1 1
1 1000
-866 287 1
1 1
3 -442 1
1 130
-628 558 0
1 868
-297 166 1
1 479
373 3 -96709
1 68
527 -833 0
1 348
-337 954 -109611
1 917
564 2 -449502
1 16
679 -175 0
1 463
138 -961 3
1 361
-951 -12 45113
1 464
-977 622 -35388
1 351...

output:

70.000000%
87.500000%
50.000000%
50.000000%
50.000000%
83.429446%
99.434389%
55.573248%
72.053484%
53.725926%
68.367347%
50.678631%
86.735384%
87.113402%
92.819305%
87.490351%
75.495542%
99.939269%
79.498817%
99.791156%
100.000000%
99.967926%
71.862629%
87.212627%
99.999999%
52.507599%
95.787352%
98...

result:

ok OK!

Test #3:

score: 0
Accepted
time: 3ms
memory: 3464kb

input:

50
4000 1000
-866 287 1
-246 141 188157
994 0 -948594
3 -442 1
172 -257 2
-77 -628 557282
-983 -297 165987
-172 -992 4695
961 587 -844056
-981 631 897222
289 1 -184824
-463 493 -336717
954 -110 32323
67 866 -240824
893 -111 -546885
259 -818 385562
906 93 -191311
308 -794 258487
502 -855 -273835
-649...

output:

100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
...

result:

ok OK!