QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #135203 | #6639. Disk Tree | SolitaryDream# | WA | 1ms | 3912kb | C++20 | 1.3kb | 2023-08-05 12:48:02 | 2023-08-05 12:48:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
struct Circle {
int x, y, r;
};
bool operator<(Circle c1, Circle c2) {
return c1.x < c2.x;
}
set<Circle> st;
map<int, vector<Circle>> mp;
signed main() {
scanf("%lld", &n);
vector<pair<int, Circle>> vec;
for (int i = 1; i <= n; ++i) {
Circle c;
scanf("%lld%lld%lld", &c.x, &c.y, &c.r);
mp[min<int>(c.y + c.r, 1e9) * 2 + 1].push_back(c);
mp[(c.y - c.r) * 2].push_back(c);
}
puts("YES");
int lx = -1, ly = -1;
for (auto it = mp.rbegin(); it != mp.rend(); ++it) {
int hei = it->first >> 1;
for (auto cir : it->second) if (it->first & 1) { // insert
// printf("Insert %lld %lld %lld\n", cir.x, cir.y, cir.r);
if (st.empty()) {
if (lx != -1) {
printf("%lld %lld %lld %lld\n", lx, ly, cir.x, hei);
}
} else {
auto ps = st.insert(cir).first;
if (ps != st.begin()) printf("%lld %lld %lld %lld\n", prev(ps)->x, hei, cir.x, hei);
else printf("%lld %lld %lld %lld\n", next(ps)->x, hei, cir.x, hei);
}
st.insert(cir);
} else {
lx = cir.x; ly = hei;
st.erase(cir);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3884kb
input:
3 1 0 3 10 10 6 0 5 1
output:
YES 10 6 0 6 0 4 1 3
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 1ms
memory: 3856kb
input:
2 1 1 1 3 3 1
output:
YES 3 2 1 2
result:
ok answer = 1
Test #3:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
5 10 10 10 2 0 1 20 20 1 3 20 1 20 0 1
output:
YES 20 21 3 21 3 20 10 20 10 1 2 1 10 1 20 1
result:
ok answer = 1
Test #4:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
10 29 29 2 28 55 10 99 81 4 17 82 10 45 88 10 48 68 10 0 8 10 98 95 10 34 0 10 17 24 10
output:
YES 98 98 45 98 45 92 17 92 98 85 99 85 45 78 48 78 48 65 28 65 28 45 17 34 17 31 29 31 17 18 0 18 0 10 34 10
result:
ok answer = 1
Test #5:
score: 0
Accepted
time: 1ms
memory: 3912kb
input:
100 490 783 12 666 460 55 561 245 6 223 323 25 3 520 77 225 161 24 514 190 16 997 914 100 412 265 100 374 610 36 296 854 39 601 901 2 307 21 100 390 422 24 940 414 32 332 438 35 553 992 100 235 775 3 656 901 37 770 417 22 649 305 100 448 84 3 375 939 77 910 847 9 776 357 37 743 97 100 371 502 39 508...
output:
YES 553 1016 375 1016 553 1014 997 1014 375 1012 67 1012 67 990 235 990 235 974 293 974 553 948 777 948 553 938 656 938 777 930 841 930 375 908 468 908 553 903 601 903 67 903 116 903 235 893 296 893 656 864 680 864 841 856 910 856 116 855 51 855 680 846 771 846 296 846 384 846 116 818 32 818 384 811...
result:
ok answer = 1
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 3672kb
input:
200 2948 9798 687 3897 647 35 3918 587 28 1262 2717 206 1315 9524 20 2381 305 1000 4344 6858 20 6234 8949 53 5168 4772 85 5044 6109 158 72 7670 132 7300 1213 837 5427 2263 1000 1785 3009 276 6136 1421 43 1629 5620 29 6445 9489 242 8443 3141 1000 4118 4307 63 1874 5238 291 1964 5785 73 7794 3934 18 3...
output:
YES 2948 10421 9505 10421 2948 10253 5225 10253 5225 10194 7511 10194 5225 10135 6125 10135 7511 10062 8438 10062 2948 9925 1844 9925 5225 9835 6062 9835 5225 9731 6445 9731 1844 9613 231 9613 231 9604 1756 9604 231 9581 462 9581 462 9544 1315 9544 231 9413 413 9413 413 9287 456 9287 8438 9282 9928 ...
result:
wrong answer Two line segments intersect, and it's not only the endpoints that intersect or line segments intersects/touches more than 2 disks