QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#335673#6734. Click the Circleucup-team1198WA 101ms4036kbC++207.9kb2024-02-23 19:22:302024-02-23 19:22:30

Judging History

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

  • [2024-02-23 19:22:30]
  • 评测
  • 测评结果:WA
  • 用时:101ms
  • 内存:4036kb
  • [2024-02-23 19:22:30]
  • 提交

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 false;
	return sqrlen(C1.c - C2.c) <= d;
}

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;
}

__int128 abs(__int128 x) {
	return x * sign(x);
}

bool point_segm_intersect_good(Point A, Point B, Point C, __int128 d) {
	assert(abs(A.x) <= 1e7);
	assert(abs(A.y) <= 1e7);
	assert(abs(B.x) <= 1e7);
	assert(abs(B.y) <= 1e7);
	assert(abs(C.x) <= 1e7);
	assert(abs(C.y) <= 1e7);
	
	if (sqrlen(A - C) <= d || sqrlen(A - B) <= d)
		return true;
	if (B == C) {
		return false;
	}
	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);
	}
	return false;
}

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);
}

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;
			}


			__int128 t1 = max(lol.t1, kek.t1);
			__int128 t2 = min(lol.t2, kek.t2);
			if (t1 > t2)
				continue;
			__int128 lol_t = lol.t2 - lol.t1;
			__int128 kek_t = kek.t2 - kek.t1;
			// up to 1e10
			Point lol_a = lol.a * lol_t * kek_t;
			Point lol_b = lol.b * lol_t * kek_t;
			Point kek_a = kek.a * lol_t * kek_t;
			Point kek_b = kek.b * lol_t * kek_t;
			// up to 1e7
			Point move_lol = (lol.b - lol.a) * kek_t;
			Point move_kek = (kek.b - kek.a) * lol_t;
			Point real_st = (lol_a + move_lol * (t1 - lol.t1)) - (kek_a + move_kek * (t1 - kek.t1));
			Point real_move = move_lol - move_kek;

			// up to 2e14
			__int128 a = sqrlen(real_move);
			// up to 4e17
			__int128 b = 2 * real_move.x * real_st.x + 2 * real_move.y * real_st.y;
			// up to 2e20
			__int128 c = sqrlen(real_st);

			__int128 mxt = t2 - t1;

			__int128 need = 4 * r * r * kek_t * kek_t * lol_t * lol_t;
			if (c <= need || a * mxt * mxt + b * mxt + c <= need) {
				++ans;
				continue;
			}
			if (a == 0) {
				continue;
			}

			// min is in the (-b/(2a))
			if (b >= 0)
				continue;
			if (-b >= 2 * a * mxt)
				continue;
			// b^2/(4a) >= c - need
			if (b * b / (4 * a) >= c - need) {
				++ans;
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3596kb

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: 0ms
memory: 3632kb

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: 3660kb

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: 3652kb

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: 3600kb

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: 30ms
memory: 3800kb

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: 3736kb

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: 30ms
memory: 3680kb

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: 40ms
memory: 3764kb

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: 30ms
memory: 4036kb

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: 43ms
memory: 3792kb

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: 101ms
memory: 4024kb

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'