QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#335654#6734. Click the Circleucup-team1198Compile Error//C++178.5kb2024-02-23 18:30:432024-02-23 18:30:44

Judging History

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

  • [2024-02-23 18:30:44]
  • 评测
  • [2024-02-23 18:30:43]
  • 提交

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

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 (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;
			bool has = false;
			long double left = 0, right = mxt;
			auto get = [&](long double x) {
				long double cur = a * x * x + b * x + c;
				if (cur <= 4 * r * r - EPS)
					has = true;
				return cur;
			};
			for (int _ = 0; _ < 50; ++_) {
				long double mid1 = (2 * left + right) / 3;
				long double mid2 = (left + 2 * right) / 3;
				if (get(mid1) <= get(mid2)) {
					right = mid2;
				} else {
					left = mid1;
				}
			}
			ans += has;
		}
	}
	cout << ans << '\n';
	return 0;
}

详细

In file included from /usr/include/c++/13/cassert:44,
                 from answer.code:10:
answer.code: In function ‘bool point_segm_intersect_good(Point, Point, Point, __int128)’:
answer.code:108:19: error: call of overloaded ‘abs(__int128&)’ is ambiguous
  108 |         assert(abs(A.x) <= 1e7);
      |                ~~~^~~~~
In file included from /usr/include/c++/13/bits/std_abs.h:38,
                 from /usr/include/c++/13/cmath:49,
                 from answer.code:4:
/usr/include/stdlib.h:840:12: note: candidate: ‘int abs(int)’
  840 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
/usr/include/c++/13/bits/std_abs.h:79:3: note: candidate: ‘constexpr long double std::abs(long double)’
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:75:3: note: candidate: ‘constexpr float std::abs(float)’
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:71:3: note: candidate: ‘constexpr double std::abs(double)’
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:61:3: note: candidate: ‘long long int std::abs(long long int)’
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:56:3: note: candidate: ‘long int std::abs(long int)’
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
answer.code:109:19: error: call of overloaded ‘abs(__int128&)’ is ambiguous
  109 |         assert(abs(A.y) <= 1e7);
      |                ~~~^~~~~
/usr/include/stdlib.h:840:12: note: candidate: ‘int abs(int)’
  840 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
/usr/include/c++/13/bits/std_abs.h:79:3: note: candidate: ‘constexpr long double std::abs(long double)’
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:75:3: note: candidate: ‘constexpr float std::abs(float)’
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:71:3: note: candidate: ‘constexpr double std::abs(double)’
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:61:3: note: candidate: ‘long long int std::abs(long long int)’
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:56:3: note: candidate: ‘long int std::abs(long int)’
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
answer.code:110:19: error: call of overloaded ‘abs(__int128&)’ is ambiguous
  110 |         assert(abs(B.x) <= 1e7);
      |                ~~~^~~~~
/usr/include/stdlib.h:840:12: note: candidate: ‘int abs(int)’
  840 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
/usr/include/c++/13/bits/std_abs.h:79:3: note: candidate: ‘constexpr long double std::abs(long double)’
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:75:3: note: candidate: ‘constexpr float std::abs(float)’
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:71:3: note: candidate: ‘constexpr double std::abs(double)’
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:61:3: note: candidate: ‘long long int std::abs(long long int)’
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:56:3: note: candidate: ‘long int std::abs(long int)’
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
answer.code:111:19: error: call of overloaded ‘abs(__int128&)’ is ambiguous
  111 |         assert(abs(B.y) <= 1e7);
      |                ~~~^~~~~
/usr/include/stdlib.h:840:12: note: candidate: ‘int abs(int)’
  840 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
/usr/include/c++/13/bits/std_abs.h:79:3: note: candidate: ‘constexpr long double std::abs(long double)’
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:75:3: note: candidate: ‘constexpr float std::abs(float)’
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:71:3: note: candidate: ‘constexpr double std::abs(double)’
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:61:3: note: candidate: ‘long long int std::abs(long long int)’
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:56:3: note: candidate: ‘long int std::abs(long int)’
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
answer.code:112:19: error: call of overloaded ‘abs(__int128&)’ is ambiguous
  112 |         assert(abs(C.x) <= 1e7);
      |                ~~~^~~~~
/usr/include/stdlib.h:840:12: note: candidate: ‘int abs(int)’
  840 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
/usr/include/c++/13/bits/std_abs.h:79:3: note: candidate: ‘constexpr long double std::abs(long double)’
   79 |   abs(long double ...