QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#335263 | #6734. Click the Circle | ucup-team1198 | WA | 74ms | 3972kb | C++17 | 8.3kb | 2024-02-23 04:04:55 | 2024-02-23 04:04:55 |
Judging History
answer
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
struct Point{
__int128 x, y;
//Point(__int128 x, __int128 y): x(x), y(y) {}
Point(__int128 x, __int128 y): x(x), y(y) {}
Point(): x(0), y(0) {}
};
Point operator+(const Point& first, const Point& second) {
return Point(first.x + second.x, first.y + second.y);
}
Point operator-(const Point& first, const Point& second) {
return Point(first.x - second.x, first.y - second.y);
}
__int128 cross(const Point& first, const Point& second) {
return first.x * second.y - first.y * second.x;
}
__int128 dot(const Point& first, const Point& second) {
return first.x * second.x + first.y * second.y;
}
__int128 sqrlen(const Point& P) {
return P.x * P.x + P.y * P.y;
}
Point operator*(const Point& A, __int128 c) {
return Point(A.x * c, A.y * c);
}
bool operator==(const Point& P, const Point& Q) {
return P.x == Q.x && P.y == Q.y;
}
void print(Point P) {
cout << int(P.x) << ' ' << int(P.y) << '\n';
}
void print(__int128 x) {
cout << int(x) << '\n';
}
__int128 r, d;
struct Circle {
Point c;
__int128 t1, t2;
Circle(Point c, __int128 t1, __int128 t2): c(c), t1(t1), t2(t2) {}
};
struct MoveCircle {
Point a, b;
__int128 t1, t2;
MoveCircle(Point a, Point b, __int128 t1, __int128 t2): a(a), b(b), t1(t1), t2(t2) {}
};
bool circles_intersect_good(Circle C1, Circle C2, __int128 d) {
__int128 t1 = max(C1.t1, C2.t1);
__int128 t2 = min(C1.t2, C2.t2);
if (t1 <= t2)
return sqrlen(C1.c - C2.c) <= d;
return false;
}
struct Line{
__int128 a;
__int128 b;
__int128 c;
Line(Point A, Point B) {
a = A.y - B.y;
b = B.x - A.x;
c = -a * A.x - b * A.y;
}
__int128 at(Point P) {
return a * P.x + b * P.y + c;
}
};
__int128 sign(__int128 x) {
if (x > 0)
return 1;
if (x < 0)
return -1;
return 0;
}
bool point_segm_intersect_good(Point A, Point B, Point C, __int128 d) {
if (B == C) {
return sqrlen(A - B) <= d;
}
if (dot(A - B, C - B) >= 0 && dot(A - C, B - C) >= 0) {
Line l(B, C);
return l.at(A) * l.at(A) <= d * (l.a * l.a + l.b * l.b); // might overflow
}
return min(sqrlen(A - C), sqrlen(A - B)) <= d;
}
bool segm_segm_intersect_good(Point A, Point B, Point C, Point D, __int128 d) {
if (point_segm_intersect_good(A, C, D, d) || point_segm_intersect_good(B, C, D, d) || point_segm_intersect_good(C, A, B, d) || point_segm_intersect_good(D, A, B, d))
return true;
if (A == B)
return false;
if (C == D)
return false;
Line l1(A, B);
Line l2(C, D);
if (sign(l1.at(C)) * sign(l1.at(D)) <= 0 && sign(l2.at(A)) * sign(l2.at(B)) <= 0)
return true;
return false;
}
bool slider_with_circle(Circle C, MoveCircle k) {
__int128 t1 = max(C.t1, k.t1 - d);
__int128 t2 = min(C.t2, k.t2 + d);
if (t1 > t2)
return false;
return point_segm_intersect_good(C.c, k.a, k.b, 4 * r * r);
}
bool circle_moving_circle(Circle C, MoveCircle k) {
Circle kek1(k.a, k.t1 - d, k.t1);
Circle kek2(k.b, k.t2, k.t2 + d);
if (circles_intersect_good(C, kek1, 4 * r * r)) {
return true;
}
if (circles_intersect_good(C, kek2, 4 * r * r)) {
return true;
}
__int128 to_mul = k.t2 - k.t1;
Point P = C.c * to_mul;
Point delta = k.b - k.a;
Point A = k.a * to_mul;
Point B = k.b * to_mul;
__int128 t1 = max(C.t1, k.t1);
__int128 t2 = min(C.t2, k.t2);
if (t1 > t2)
return false;
A = A + delta * (t1 - k.t1);
B = B - delta * (k.t2 - t2);
return point_segm_intersect_good(P, A, B, 4 * r * r * to_mul * to_mul);
}
pair<long double, long double> make_cringe(Point P) {
return make_pair((long double)P.x, (long double)P.y);
}
pair<long double, long double> operator-(const pair<long double, long double>& a, const pair<long double, long double>& b) {
return make_pair(a.first - b.first, a.second - b.second);
}
pair<long double, long double> operator+(const pair<long double, long double>& a, const pair<long double, long double>& b) {
return make_pair(a.first + b.first, a.second + b.second);
}
pair<long double, long double> operator*(const pair<long double, long double>& a, long double c) {
return make_pair(a.first * c, a.second * c);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, rr, dd;
cin >> n >> rr >> dd;
r = rr;
d = dd;
vector<Circle> circles;
vector<MoveCircle> move_circles;
for (int i = 0; i < n; ++i) {
int t;
cin >> t;
if (t == 1) {
int x, y, t;
cin >> x >> y >> t;
circles.emplace_back(Point(x, y), t - d, t + d);
} else {
int x1, y1, x2, y2, u, v;
cin >> x1 >> y1 >> x2 >> y2 >> u >> v;
move_circles.emplace_back(Point(x1, y1), Point(x2, y2), u, v);
}
}
int ans = 0;
// circle with circle
for (int i = 0; i < circles.size(); ++i) {
for (int j = 0; j < i; ++j) {
Circle C1 = circles[i];
Circle C2 = circles[j];
if (circles_intersect_good(C1, C2, 4 * r * r))
++ans;
}
}
// circle with moving
for (Circle C : circles) {
for (MoveCircle k : move_circles) {
ans += circle_moving_circle(C, k);
}
}
// circle with slider
for (Circle C : circles) {
for (MoveCircle k : move_circles) {
ans += slider_with_circle(C, k);
}
}
// slider with slider
for (int i = 0; i < move_circles.size(); ++i) {
for (int j = 0; j < i; ++j) {
auto lol = move_circles[i];
auto kek = move_circles[j];
__int128 t1 = max(lol.t1 - d, kek.t1 - d);
__int128 t2 = min(lol.t2 + d, kek.t2 + d);
if (t1 <= t2) {
ans += segm_segm_intersect_good(lol.a, lol.b, kek.a, kek.b, 4 * r * r);
}
}
}
// slider with moving
for (auto lol : move_circles) {
for (auto kek : move_circles) {
if (slider_with_circle(Circle(kek.a, kek.t1 - d, kek.t1), lol)) {
++ans;
continue;
}
if (slider_with_circle(Circle(kek.b, kek.t2, kek.t2 + d), lol)) {
++ans;
continue;
}
__int128 to_mul = kek.t2 - kek.t1;
Point delta = kek.b - kek.a;
__int128 t1 = max(lol.t1 - d, kek.t1);
__int128 t2 = min(lol.t2 + d, kek.t2);
if (t1 > t2)
continue;
Point A = kek.a * to_mul + delta * (t1 - kek.t1);
Point B = kek.b * to_mul - delta * (kek.t2 - t2);
if (segm_segm_intersect_good(lol.a * to_mul, lol.b * to_mul, A, B, 4 * r * r * to_mul * to_mul)) {
++ans;
}
}
}
// moving with moving
for (int i = 0; i < move_circles.size(); ++i) {
for (int j = 0; j < i; ++j) {
auto lol = move_circles[i];
Circle lol1(lol.a, lol.t1 - d, lol.t1);
Circle lol2(lol.b, lol.t2, lol.t2 + d);
auto kek = move_circles[j];
Circle kek1(kek.a, kek.t1 - d, kek.t1);
Circle kek2(kek.b, kek.t2, kek.t2 + d);
if (circle_moving_circle(lol1, kek) || circle_moving_circle(lol2, kek) ||
circle_moving_circle(kek1, lol) || circle_moving_circle(kek2, lol)) {
++ans;
continue;
}
const long double EPS = 1e-8;
__int128 t1 = max(lol.t1, kek.t1);
__int128 t2 = min(lol.t2, kek.t2);
if (t1 > t2)
continue;
auto lol_a = make_cringe(lol.a);
auto lol_b = make_cringe(lol.b);
auto kek_a = make_cringe(kek.a);
auto kek_b = make_cringe(kek.b);
auto move1 = (lol_b - lol_a) * ((long double)(1.0) / (lol.t2 - lol.t1));
auto move2 = (kek_b - kek_a) * ((long double)(1.0) / (kek.t2 - kek.t1));
lol_a = lol_a + move1 * ((long double)(t1 - lol.t1));
kek_a = kek_a + move2 * ((long double)(t1 - kek.t1));
auto p1 = lol_a - kek_a;
auto move = move1 - move2;
long double mxt = t2 - t1;
long double a = (move.first * move.first + move.second * move.second);
long double b = 2 * move.first * p1.first + 2 * move.second * p1.second;
long double c = p1.first * p1.first + p1.second * p1.second;
if (c <= 4 * r * r + EPS) {
++ans;
continue;
}
if (a * mxt * mxt + b * mxt + c <= 4 * r * r + EPS) {
++ans;
continue;
}
if (abs(a) < EPS)
continue;
long double opt = -b / 2 / a;
if (-EPS <= opt && opt <= mxt + EPS) {
if (a * opt * opt + b * opt + c <= 4 * r * r + EPS) {
++ans;
}
}
}
}
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3816kb
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: 3816kb
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: 0ms
memory: 3544kb
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: 3576kb
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: 0ms
memory: 3504kb
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: 3740kb
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: 24ms
memory: 3680kb
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: 27ms
memory: 3732kb
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: 35ms
memory: 3768kb
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: 29ms
memory: 3760kb
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: 33ms
memory: 3692kb
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: -100
Wrong Answer
time: 74ms
memory: 3972kb
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:
163893
result:
wrong answer 1st numbers differ - expected: '163887', found: '163893'