QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#471628 | #9103. Zayin and Fireball | real_sigma_team# | TL | 0ms | 0kb | C++17 | 2.7kb | 2024-07-10 23:37:46 | 2024-09-23 15:03:55 |
Judging History
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...