QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#129884 | #6734. Click the Circle | UndertrainedOverpressure | AC ✓ | 182ms | 3684kb | C++23 | 7.0kb | 2023-07-23 02:35:09 | 2023-07-23 02:35:11 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)
// _________ vect (2D) ______________
template <typename T>
struct vect {
T x = 0;
T y = 0;
vect() = default;
vect(T x_, T y_) : x(x_), y(y_) {}
inline T len2() const {
return x * x + y * y;
}
inline ld len() const {
return sqrtl(len2());
}
inline vect rotate() const {
return vect(-y, x);
}
};
template <typename T>
inline istream& operator>>(istream& in, vect<T>& v) {
return in >> v.x >> v.y;
}
template <typename T>
inline ostream& operator<<(ostream& out, const vect<T>& v) {
return out << "[" << v.x << "," << v.y << "]";
}
template <typename T>
inline vect<T> operator+(const vect<T>& a, const vect<T>& b) {
return vect(a.x + b.x, a.y + b.y);
}
template <typename T>
inline vect<T> operator-(const vect<T>& a, const vect<T>& b) {
return vect(a.x - b.x, a.y - b.y);
}
template <typename T>
inline vect<T> operator*(const vect<T>& a, T k) {
return vect(a.x * k, a.y * k);
}
template <typename T>
inline T operator*(const vect<T>& a, const vect<T>& b) {
return a.x * b.x + a.y * b.y;
}
template <typename T>
inline T operator^(const vect<T>& a, const vect<T>& b) {
return a.x * b.y - a.y * b.x;
}
template <typename T>
inline bool operator==(const vect<T>& a, const vect<T>& b) {
return a.x == b.x && a.y == b.y;
}
struct tubus {
vect<ll> a, b;
int L, R;
tubus(vect<ll> a, vect<ll> b, int L, int R) : a(a), b(b), L(L), R(R) {}
};
__int128 abs(__int128 x) {
if (x < 0) {
return -x;
}
return x;
}
bool check(vect<__int128> a, vect<__int128> b, vect<__int128> c, __int128 r) {
if (b == c) {
return (a - b).len2() <= r * r;
}
__int128 mn = min((a - b).len2(), (a - c).len2());
if (((a - b) * (c - b)) <= 0 || ((a - c) * (b - c)) <= 0) {
return mn <= r * r;
}
__int128 area = abs((b - a) ^ (c - a));
assert(area <= (__int128)(1e19));
assert((b - c).len2() <= (__int128)(1e19));
assert(r * r <= (__int128)(1e19));
return area * area <= (b - c).len2() * r * r;
}
bool on_seg(vect<__int128> a, vect<__int128> b, vect<__int128> c) {
return ((a - c) ^ (b - c)) == 0 && ((a - c) * (b - c)) <= 0;
}
int sign(__int128 x) {
if (x < 0) {
return -1;
}
if (x == 0) {
return 0;
}
return 1;
}
bool check(vect<ll> aa, vect<ll> bb, vect<ll> cc, vect<ll> dd, __int128 r) {
vect<__int128> a(aa.x, aa.y);
vect<__int128> b(bb.x, bb.y);
vect<__int128> c(cc.x, cc.y);
vect<__int128> d(dd.x, dd.y);
if (a == b) {
return check(a, c, d, r);
}
if (c == d) {
return check(c, a, b, r);
}
if (on_seg(a, b, c) || on_seg(a, b, d) || on_seg(c, d, a) || on_seg(c, d, b)) {
return true;
}
bool ch = true;
if (((a - c) ^ (b - c)) == 0) {
ch = false;
}
if (((a - d) ^ (b - d)) == 0) {
ch = false;
}
if (((c - a) ^ (d - a)) == 0) {
ch = false;
}
if (((c - b) ^ (d - b)) == 0) {
ch = false;
}
if (ch && sign((c - a) ^ (d - a)) != sign((c - b) ^ (d - b)) && sign((a - c) ^ (b - c)) != sign((a - d) ^ (b - d))) {
return true;
}
return check(a, c, d, r) || check(b, c, d, r) || check(c, a, b, r) || check(d, a, b, r);
}
bool check_tb_tb(tubus t1, tubus t2, int r) {
if (t1.R < t2.L || t2.R < t1.L) {
return false;
}
return check(t1.a, t1.b, t2.a, t2.b, r);
}
bool check_tb_run(tubus t1, tubus t2, ll r, int d) {
if (check_tb_tb(t1, tubus(t2.a, t2.a, t2.L - d, t2.L), r)) {
return true;
}
if (check_tb_tb(t1, tubus(t2.b, t2.b, t2.R, t2.R + d), r)) {
return true;
}
int seg_l = max(t1.L, t2.L);
int seg_r = min(t1.R, t2.R);
if (seg_l > seg_r) {
return false;
}
r *= (ll)(t2.R - t2.L);
t1.a = t1.a * (ll)(t2.R - t2.L);
t1.b = t1.b * (ll)(t2.R - t2.L);
auto new_a = t2.a * (ll)(t2.R - seg_l) + t2.b * (ll)(seg_l - t2.L);
auto new_b = t2.a * (ll)(t2.R - seg_r) + t2.b * (ll)(seg_r - t2.L);
t2.a = new_a;
t2.b = new_b;
return check(t1.a, t1.b, t2.a, t2.b, r);
}
bool check_run_run(tubus t1, tubus t2, ll r, int d) {
if (check_tb_run(tubus(t1.a, t1.a, t1.L - d, t1.L), t2, r, d)) {
return true;
}
if (check_tb_run(tubus(t1.b, t1.b, t1.R, t1.R + d), t2, r, d)) {
return true;
}
if (check_tb_run(tubus(t2.a, t2.a, t2.L - d, t2.L), t1, r, d)) {
return true;
}
if (check_tb_run(tubus(t2.b, t2.b, t2.R, t2.R + d), t1, r, d)) {
return true;
}
int seg_l = max(t1.L, t2.L);
int seg_r = min(t1.R, t2.R);
if (seg_l > seg_r) {
return false;
}
r *= (ll)(t2.R - t2.L) * (ll)(t1.R - t1.L);
t1.a = t1.a * (ll)(t2.R - t2.L);
t1.b = t1.b * (ll)(t2.R - t2.L);
t2.a = t2.a * (ll)(t1.R - t1.L);
t2.b = t2.b * (ll)(t1.R - t1.L);
{
auto new_a = t2.a * (ll)(t2.R - seg_l) + t2.b * (ll)(seg_l - t2.L);
auto new_b = t2.a * (ll)(t2.R - seg_r) + t2.b * (ll)(seg_r - t2.L);
t2.a = new_a;
t2.b = new_b;
}
{
auto new_a = t1.a * (ll)(t1.R - seg_l) + t1.b * (ll)(seg_l - t1.L);
auto new_b = t1.a * (ll)(t1.R - seg_r) + t1.b * (ll)(seg_r - t1.L);
t1.a = new_a;
t1.b = new_b;
}
return check(vect<ll>(), vect<ll>(), t2.a - t1.a, t2.b - t1.b, r);
}
void solve() {
int n, r, d;
cin >> n >> r >> d;
r *= 2;
vector<tubus> tb, run;
for (int i = 0; i < n; i++) {
int type;
cin >> type;
if (type == 1) {
vect<ll> c;
int t;
cin >> c >> t;
tb.emplace_back(c, c, t - d, t + d);
} else {
vect<ll> c, s;
int u, v;
cin >> c >> s >> u >> v;
tb.emplace_back(c, s, u - d, v + d);
run.emplace_back(c, s, u, v);
}
}
int ans = 0;
for (int i = 0; i < tb.size(); i++) {
for (int j = i + 1; j < tb.size(); j++) {
if (check_tb_tb(tb[i], tb[j], r)) {
ans++;
}
}
}
for (int i = 0; i < tb.size(); i++) {
for (int j = 0; j < run.size(); j++) {
if (check_tb_run(tb[i], run[j], r, d)) {
ans++;
}
}
}
for (int i = 0; i < run.size(); i++) {
for (int j = i + 1; j < run.size(); j++) {
if (check_run_run(run[i], run[j], r, d)) {
ans++;
}
}
}
cout << ans << "\n";
}
int main() {
#ifdef ONPC
freopen("input", "r", stdin);
#endif
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3548kb
input:
2 1 1 1 1 1 2 1 2 2 3
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3484kb
input:
2 1 1 1 1 1 2 1 3 2 3
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
2 1 1 1 3 3 2 2 5 5 5 1 2 4
output:
3
result:
ok 1 number(s): "3"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
2 1 1 2 1 1 1 5 2 4 2 5 5 5 1 2 4
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
2 1 1 2 10 1 10 20 2 4 2 1 10 20 10 2 4
output:
6
result:
ok 1 number(s): "6"
Test #6:
score: 0
Accepted
time: 27ms
memory: 3564kb
input:
1000 8 4 1 8323 2820 943 1 8246 2850 944 1 8177 2880 941 1 8154 2866 944 2 8325 8146 2865 2846 943 944 1 8349 2891 939 2 8176 8344 2888 2692 940 945 1 8191 2732 945 1 8144 2668 945 2 8182 8191 2889 2844 939 940 1 8173 2687 941 1 8241 2870 945 2 8266 8344 2910 2667 942 943 1 8169 2863 939 1 8349 2921...
output:
22721
result:
ok 1 number(s): "22721"
Test #7:
score: 0
Accepted
time: 26ms
memory: 3592kb
input:
1000 35 8 2 1037 1102 9971 9940 531 534 1 301 9951 548 1 944 9962 529 1 592 9968 537 1 262 9949 531 1 312 9971 553 1 1139 9938 550 2 325 747 9967 9970 539 544 1 810 9941 536 2 906 486 9956 9953 550 552 1 1121 9940 543 2 515 1199 9965 9953 548 552 2 537 926 9972 9949 538 547 1 1356 9967 550 1 332 996...
output:
34559
result:
ok 1 number(s): "34559"
Test #8:
score: 0
Accepted
time: 34ms
memory: 3684kb
input:
1000 472 14 1 3783 7912 938 1 3307 7801 773 1 4605 7852 592 1 2999 7886 644 1 5308 7914 865 1 4978 7842 611 2 3205 5292 7915 7915 724 835 1 6173 7919 846 2 3130 4833 7921 7853 893 906 1 3449 7854 938 2 4951 3238 7824 7897 720 874 2 4842 5378 7906 7913 683 853 2 4991 4467 7906 7830 580 779 2 5782 615...
output:
103238
result:
ok 1 number(s): "103238"
Test #9:
score: 0
Accepted
time: 50ms
memory: 3644kb
input:
1000 4 51 2 6933 7307 7777 7798 450 456 2 6444 6705 7787 7794 447 460 1 7192 7784 464 2 7865 6422 7791 7797 451 460 1 7366 7794 461 2 7364 6214 7785 7782 449 454 2 7378 7099 7801 7798 450 461 2 7961 6794 7784 7788 448 449 2 6510 7007 7787 7797 453 458 1 6517 7786 446 2 6725 7216 7797 7788 451 452 2 ...
output:
36558
result:
ok 1 number(s): "36558"
Test #10:
score: 0
Accepted
time: 28ms
memory: 3596kb
input:
1000 27 6 2 3760 3746 1523 1749 339 366 2 3738 3746 1688 1609 334 356 1 3754 1559 349 1 3761 1551 347 2 3746 3755 1667 1528 338 340 2 3754 3749 1565 1664 331 356 2 3746 3759 1653 1674 357 362 2 3753 3739 1741 1625 346 359 2 3763 3747 1701 1738 340 343 2 3742 3754 1695 1759 361 366 2 3742 3752 1654 1...
output:
36245
result:
ok 1 number(s): "36245"
Test #11:
score: 0
Accepted
time: 70ms
memory: 3568kb
input:
1000 78 150 1 6600 430 535 1 6589 476 532 2 6596 6596 430 489 530 533 2 6598 6601 469 470 529 531 1 6597 495 534 1 6597 474 533 2 6592 6599 467 465 536 538 2 6600 6596 460 484 535 537 1 6587 461 529 2 6596 6596 431 485 532 533 1 6597 465 538 2 6591 6597 429 465 530 534 1 6598 439 533 2 6596 6588 458...
output:
92999
result:
ok 1 number(s): "92999"
Test #12:
score: 0
Accepted
time: 182ms
memory: 3620kb
input:
1000 19 854 1 4584 7521 143 1 4587 7497 142 2 4587 4582 7516 7363 145 147 2 4591 4585 7360 7370 143 147 2 4582 4589 7491 7418 145 147 1 4592 7366 145 2 4587 4585 7402 7375 142 143 2 4584 4585 7392 7516 145 147 2 4584 4587 7383 7502 142 147 1 4583 7462 145 1 4592 7461 146 1 4588 7409 142 2 4591 4590 ...
output:
163887
result:
ok 1 number(s): "163887"
Test #13:
score: 0
Accepted
time: 172ms
memory: 3664kb
input:
1000 38 834 2 727 740 7904 8009 721 901 2 771 686 7753 7896 707 714 2 790 766 7801 7864 877 919 1 790 7902 874 2 709 686 7990 7998 739 760 1 666 7941 849 2 677 726 8009 7939 810 820 2 679 686 7896 7935 810 923 2 747 718 8018 7963 700 786 1 719 7987 825 1 697 7975 931 1 764 7794 847 1 659 7813 813 1 ...
output:
203301
result:
ok 1 number(s): "203301"
Test #14:
score: 0
Accepted
time: 28ms
memory: 3560kb
input:
1000 767 32 2 615 605 4677 4694 404 408 1 620 4687 421 1 617 4681 452 1 621 4687 436 2 609 608 4698 4678 404 433 2 603 620 4690 4680 391 419 2 604 609 4682 4678 405 428 1 615 4678 443 2 615 611 4678 4698 402 413 1 614 4692 450 2 601 616 4695 4692 441 442 1 614 4674 401 1 617 4697 420 1 606 4698 423 ...
output:
104679
result:
ok 1 number(s): "104679"
Test #15:
score: 0
Accepted
time: 23ms
memory: 3612kb
input:
1000 68 9 1 4226 6175 121 2 4232 4221 5792 5879 82 102 1 4226 6152 69 1 4226 5910 69 2 4238 4242 6314 6215 70 74 1 4233 6208 149 1 4247 5765 162 2 4237 4221 5787 5877 180 192 1 4223 5966 148 1 4221 5925 111 2 4241 4245 6105 6069 173 203 1 4234 6275 108 1 4230 5952 166 1 4247 5925 214 1 4220 6288 192...
output:
43227
result:
ok 1 number(s): "43227"
Test #16:
score: 0
Accepted
time: 166ms
memory: 3644kb
input:
1000 20 500 2 9234 9242 4563 4578 972 976 2 9230 9142 4582 4551 972 973 1 9207 4564 971 1 9246 4561 973 2 9228 9253 4564 4571 976 977 1 9132 4566 973 2 9207 9273 4564 4582 970 982 2 9182 9172 4552 4583 965 970 2 9241 9248 4561 4564 965 966 1 9160 4570 978 1 9171 4573 978 1 9288 4564 977 2 9124 9209 ...
output:
168341
result:
ok 1 number(s): "168341"
Test #17:
score: 0
Accepted
time: 50ms
memory: 3684kb
input:
1000 479 93 2 3917 4659 8054 8309 907 919 1 3652 8108 917 1 3807 8421 889 1 3809 7956 918 2 5455 6444 8146 7993 888 897 1 3919 8428 896 1 5806 8417 904 1 5003 8284 908 1 4433 8111 900 2 4758 5119 8171 8370 893 917 1 5167 8085 909 2 5355 4401 8243 8214 894 902 2 4998 6113 8049 7961 901 905 2 6438 588...
output:
130628
result:
ok 1 number(s): "130628"
Test #18:
score: 0
Accepted
time: 53ms
memory: 3596kb
input:
1000 9 64 2 4598 4157 749 771 946 951 2 3869 4053 744 756 946 957 1 3637 785 963 2 4680 4023 760 797 949 950 2 3674 3955 743 759 949 951 1 4442 794 951 2 4336 4099 806 743 946 962 1 4544 787 962 2 4316 4548 743 802 956 963 1 3582 768 949 1 4230 794 955 2 4477 4446 778 780 957 958 2 3758 4306 751 781...
output:
35598
result:
ok 1 number(s): "35598"
Test #19:
score: 0
Accepted
time: 36ms
memory: 3564kb
input:
1000 57 27 1 7434 3356 642 2 7427 7433 3355 3354 669 684 2 7432 7435 3353 3354 683 778 1 7424 3356 772 2 7434 7421 3356 3351 727 803 2 7432 7420 3355 3352 672 695 2 7426 7421 3353 3354 630 656 2 7425 7420 3352 3355 696 701 1 7428 3352 720 1 7429 3355 692 1 7433 3353 714 1 7430 3355 838 2 7432 7420 3...
output:
61871
result:
ok 1 number(s): "61871"
Test #20:
score: 0
Accepted
time: 116ms
memory: 3568kb
input:
1000 883 463 1 2380 6779 801 2 1342 1303 6814 6780 800 801 2 263 1224 6797 6792 801 803 2 623 427 6787 6793 801 803 2 398 2034 6801 6790 802 803 1 1521 6782 800 1 1090 6807 803 1 575 6806 799 2 998 1435 6782 6788 801 803 1 811 6799 800 2 1509 1567 6783 6779 799 800 1 1156 6812 800 1 294 6802 800 1 1...
output:
522826
result:
ok 1 number(s): "522826"
Test #21:
score: 0
Accepted
time: 162ms
memory: 3632kb
input:
1000 1 430 2 9469 9548 8535 8853 127 180 1 9510 9271 108 1 9417 9255 118 1 9603 9094 127 1 9416 8441 120 2 9591 9501 9100 9100 147 198 2 9413 9551 8606 8240 216 223 2 9506 9525 8715 9157 80 152 1 9559 8977 42 1 9552 9286 54 2 9555 9551 8424 9279 37 131 1 9376 9085 61 2 9488 9543 9140 9374 87 222 2 9...
output:
59834
result:
ok 1 number(s): "59834"
Test #22:
score: 0
Accepted
time: 15ms
memory: 3644kb
input:
1000 49 3 2 8881 8913 1885 2159 225 239 1 8883 1980 245 2 8908 8883 2082 2199 223 254 2 8903 8905 2170 2048 229 247 1 8882 1944 225 1 8910 1844 247 2 8887 8902 2034 2080 232 233 1 8887 2082 250 1 8901 1908 251 2 8899 8884 1884 2112 242 245 1 8889 1914 254 1 8899 2188 250 2 8908 8881 2071 2019 239 24...
output:
24042
result:
ok 1 number(s): "24042"
Test #23:
score: 0
Accepted
time: 163ms
memory: 3592kb
input:
1000 51 968 1 3531 6961 345 1 4472 7149 357 1 2691 6615 359 2 3325 4548 7314 6828 356 358 2 4801 3905 6987 6647 358 372 1 4974 6876 366 1 4527 6792 344 2 3363 3335 7054 7147 359 365 1 2922 6705 375 1 4487 7293 355 2 3236 4914 6926 6782 346 374 1 4463 6740 369 1 2796 6833 361 1 3969 6830 358 1 4665 7...
output:
274214
result:
ok 1 number(s): "274214"
Test #24:
score: 0
Accepted
time: 31ms
memory: 3660kb
input:
1000 1 10 2 5234 5378 7146 7016 658 806 2 3852 5355 6863 6990 837 883 2 3953 3596 7007 6909 701 756 1 6504 6967 920 2 4033 5760 6873 7090 674 869 2 4163 4267 7178 6938 864 912 1 3622 6948 938 1 5798 7146 824 1 4829 7126 786 1 4400 6989 775 1 4738 6933 854 2 4230 5240 6863 7148 711 796 1 3987 7172 84...
output:
15333
result:
ok 1 number(s): "15333"
Test #25:
score: 0
Accepted
time: 39ms
memory: 3660kb
input:
1000 614 50 2 2448 2538 7136 7095 541 552 1 2348 7052 565 1 2498 7085 554 2 2313 2444 7132 7152 552 564 1 2300 7021 560 1 2289 7066 553 2 2572 2547 7122 7067 551 563 2 2473 2462 7054 7062 556 563 1 2290 7046 553 2 2397 2493 7134 7053 547 550 1 2312 7049 551 2 2595 2448 7085 7113 549 557 2 2432 2314 ...
output:
133247
result:
ok 1 number(s): "133247"