QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#471628#9103. Zayin and Fireballreal_sigma_team#TL 0ms0kbC++172.7kb2024-07-10 23:37:462024-09-23 15:03:55

Judging History

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

  • [2024-09-23 15:03:55]
  • 管理员手动重测本题所有提交记录
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-07-10 23:37:46]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-07-10 23:37:46]
  • 提交

answer

#include<bits/stdc++.h>

//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")

using namespace std;


//#define double long double

struct circle {
    int x, y, r;
};

pair<circle, circle> v[500];

bool in(circle c, double x, double y) {
    return (x - c.x) * (x - c.x) + (y - c.y) * (y - c.y) <= c.r * c.r;
}

bool all_in(circle c, double lx, double rx, double ly, double ry) {
    bool res = true;
    for (auto x : {lx, rx}) {
        for (auto y : {ly, ry}) {
            res &= in(c, x, y);
        }
    }
    return res;
}

bool inter(circle c, double lx, double rx, double ly, double ry) {
    bool res = (lx <= c.x && c.x <= rx) && (ly <= c.y && c.y <= ry);
    for (auto x : {lx, rx}) {
        for (auto y : {ly, ry}) {
            res |= in(c, x, y);
        }
    }
    if (lx <= c.x && c.x <= rx) {
        res |= in(c, c.x, ly) || in(c, c.x, ry);
    }
    if (ly <= c.y && c.y <= ry) {
        res |= in(c, lx, c.y) || in(c, rx, c.y);
    }
    return res;
}

double res = 0;

const int K = 2;

void rec(double lx, double rx, double ly, double ry, vector<int> circles) {
//    cout << lx << ' ' << rx << ' ' << ly << ' ' << ry << endl;
    if (rx - lx < 1e-4) return;
    bool q = false;
    vector<int> nxt;
    for (auto id : circles) {
        if (all_in(v[id].first, lx, rx, ly, ry) && !inter(v[id].second, lx, rx, ly, ry)) q = true;
        if (inter(v[id].first, lx, rx, ly, ry) && !all_in(v[id].second, lx, rx, ly, ry)) nxt.push_back(id);
    }
    if (q) {
        res += (rx - lx) * (ry - ly);
        return;
    }
    if (nxt.empty()) {
        return;
    }
    double dx = (rx - lx) / K;
    double dy = (ry - ly) / K;
    for (int i = 0; i < K; ++i) {
        for (int j = 0; j < K; ++j) {
            rec(lx + i * dx, lx + (i + 1) * dx, ly + j * dy, ly + (j + 1) * dy, circles);
        }
    }
}


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cerr << fixed << setprecision(4);

//    cout << "30\n";
//    for (int i = 0; i < 30; ++i) {
//        cout << "2\n";
//        cout << "0 0 2 0 0 2\n";
//        cout << "2 2 2 233 0 51\n";
//    }
//    return 0;

    int tests;
    cin >> tests;
    auto start = clock();
    while (tests--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> v[i].first.x >> v[i].first.y >> v[i].first.r;
            cin >> v[i].second.x >> v[i].second.y >> v[i].second.r;
        }
        vector<int> p(n);
        iota(p.begin(), p.end(), 0);
        res = 0;
        rec(-(1 << 11), (1 << 11), -(1 << 11), (1 << 11), p);
        cout << res << '\n';
    }
    cerr << 1.0 * (clock() - start) / CLOCKS_PER_SEC;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

22
1
0 0 1 0 0 1
1
0 0 2 0 0 1
1
0 0 2 1 0 1
1
0 0 2 2 0 1
1
0 0 2 1 0 2
2
0 0 1 0 0 0
0 0 3 0 0 2
2
0 0 1 0 0 0
0 0 3 0 0 1
2
-233 0 3 -234 0 1
233 0 2 231 0 1
2
0 0 1 0 0 0
1 0 3 0 0 1
2
0 0 1 0 0 0
0 2 3 0 0 1
2
2 4 2 2 4 1
3 3 3 3 3 1
4
0 1 1 0 2 2
3 3 3 3 4 2
250 2 4 0 0 100
255 7 12 254 10 4
3...

output:


result: