QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#547162#3034. Antennascrimson231AC ✓684ms9516kbC++1712.3kb2024-09-04 18:48:472024-09-04 18:48:47

Judging History

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

  • [2024-09-04 18:48:47]
  • 评测
  • 测评结果:AC
  • 用时:684ms
  • 内存:9516kb
  • [2024-09-04 18:48:47]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#include <cassert>
typedef long long ll;
//typedef long double ld;
typedef double ld;
const ld INF = 1e17;
const ld TOL = 1e-7;
const ld PI = acos(-1);
const int LEN = 505;
inline int sign(const ll& x) { return x < 0 ? -1 : !!x; }
inline int sign(const ld& x) { return x < -TOL ? -1 : x > TOL; }
inline bool zero(const ld& x) { return !sign(x); }
inline ll nC2(const ll& n) { return (n - 1) * n >> 1; }

int Z, N, M, Q;
struct Pos {
	ll x, y;
	Pos(ll X = 0, ll Y = 0) : x(X), y(Y) {}
	bool operator == (const Pos& p) const { return x == p.x && y == p.y; }
	bool operator != (const Pos& p) const { return x != p.x || y != p.y; }
	bool operator < (const Pos& p) const { return x == p.x ? y < p.y : x < p.x; }
	bool operator <= (const Pos& p) const { return x == p.x ? y <= p.y : x <= p.x; }
	Pos operator + (const Pos& p) const { return { x + p.x, y + p.y }; }
	Pos operator - (const Pos& p) const { return { x - p.x, y - p.y }; }
	Pos operator * (const int& n) const { return { x * n, y * n }; }
	Pos operator / (const int& n) const { return { x / n, y / n }; }
	ll operator * (const Pos& p) const { return (ll)x * p.x + (ll)y * p.y; }
	ll operator / (const Pos& p) const { return (ll)x * p.y - (ll)y * p.x; }
	Pos operator ^ (const Pos& p) const { return { x * p.x, y * p.y }; }
	Pos& operator += (const Pos& p) { x += p.x; y += p.y; return *this; }
	Pos& operator -= (const Pos& p) { x -= p.x; y -= p.y; return *this; }
	Pos& operator *= (const int& scale) { x *= scale; y *= scale; return *this; }
	Pos& operator /= (const int& scale) { x /= scale; y /= scale; return *this; }
	Pos operator - () const { return { -x, -y }; }
	Pos operator ~ () const { return { -y, x }; }
	Pos operator ! () const { return { y, x }; }
	ll xy() const { return (ll)x * y; }
	ll Euc() const { return (ll)x * x + (ll)y * y; }
	int Man() const { return std::abs(x) + std::abs(y); }
	ld mag() const { return hypot(x, y); }
	ld rad() const { return atan2(y, x); }
	friend ld rad(const Pos& p1, const Pos& p2) { return atan2l(p1 / p2, p1 * p2); }
	int quad() const { return y > 0 || y == 0 && x >= 0; }
	friend bool cmpq(const Pos& a, const Pos& b) { return (a.quad() != b.quad()) ? a.quad() < b.quad() : a / b > 0; }
	friend std::istream& operator >> (std::istream& is, Pos& p) { is >> p.x >> p.y; return is; }
	friend std::ostream& operator << (std::ostream& os, const Pos& p) { os << p.x << " " << p.y; return os; }
}; const Pos O = Pos(0, 0);
typedef std::vector<Pos> Polygon;
ll cross(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) / (d3 - d2); }
int ccw(const Pos& d1, const Pos& d2, const Pos& d3) { ll ret = cross(d1, d2, d3); return sign(ret); }
bool cmpt(const Pos& p, const Pos& q) {
	assert(p / q);
	if (!(p / q)) return p.Euc() < q.Euc();
	return p / q > 0;
}
Polygon graham_scan(Polygon& C) {
	Polygon H;
	if (C.size() < 3) {
		std::sort(C.begin(), C.end());
		return C;
	}
	std::swap(C[0], *min_element(C.begin(), C.end()));
	std::sort(C.begin() + 1, C.end(), [&](const Pos& p, const Pos& q) -> bool {
		int ret = ccw(C[0], p, q);
		if (!ret) return (C[0] - p).Euc() < (C[0] - q).Euc();
		return ret > 0;
		}
	);
	C.erase(unique(C.begin(), C.end()), C.end());
	int sz = C.size();
	for (int i = 0; i < sz; i++) {
		while (H.size() >= 2 && ccw(H[H.size() - 2], H.back(), C[i]) <= 0)
			H.pop_back();
		H.push_back(C[i]);
	}
	return H;
}
bool inner_check(const Polygon& H, const Pos& p) {
	int sz = H.size();
	for (int i = 0; i < sz; i++) if (cross(H[i], H[(i + 1) % sz], p) < 0) return 0;
	return 1;
}
ll conquer(Polygon& C, int l, int m, int r) {
	int i = l, j = m + 1, k = 0;
	Polygon tmp(r - l + 1);
	ll cnt = 0;
	while (i <= m && j <= r) {
		if (cmpt(C[i], C[j])) tmp[k++] = C[i++];
		else tmp[k++] = C[j++], cnt += ((ll)m + 1 - i);
	}
	while (i <= m) tmp[k++] = C[i++];
	while (j <= r) tmp[k++] = C[j++];
	for (i = l, k = 0; i <= r; i++, k++) C[i] = tmp[k];
	return cnt;
}
ll divide(Polygon& C, int l, int r) {
	ll cnt = 0;
	if (l < r) {
		int m = l + r >> 1;
		cnt += divide(C, l, m);
		cnt += divide(C, m + 1, r);
		cnt += conquer(C, l, m, r);
	}
	return cnt;
}
ll merge_sort(Polygon& C) { return divide(C, 0, C.size() - 1); }
ll inv_count(Polygon& C) { ll inv = merge_sort(C); return inv; }
ll inv_count(Polygon& C, const Pos& a, const Pos& b) {
	int sz = C.size();
	ll all = nC2((ll)sz);
	for (int i = 0; i < sz; i++) C[i] -= a;
	std::sort(C.begin(), C.end(), cmpt);
	for (int i = 0; i < sz; i++) C[i] += a - b;
	ll ret = all - inv_count(C);
	for (int i = 0; i < sz; i++) C[i] += b;
	return ret;
}
void query(const Polygon& H, const Polygon& A) {
	int a_, b_;
	std::cin >> a_ >> b_;
	int sz = H.size();
	Pos a0 = H[a_], a = H[(a_ + 1) % sz], b = H[b_], b0 = H[(b_ + 1) % sz];
	/*
	   a --- b         a == b      a - b
	   |     |   ||   / \      ||   \ /
	   a0 -- b0      a0 b0           a0 == b0
	*/
	Polygon S = { a0, a, b, b0 }, P;
	Polygon B = graham_scan(S);
	sz = A.size();
	for (int i = 0; i < sz; i++) if (inner_check(B, A[i])) P.push_back(A[i]);
	Polygon ab, a0b, ab0;
	sz = P.size();
	for (int i = 0; i < sz; i++) {
		if (ccw(b, a, P[i]) >= 0) ab.push_back(P[i]);
		if (ccw(b0, a, P[i]) >= 0) ab0.push_back(P[i]);
		if (ccw(b, a0, P[i]) >= 0) a0b.push_back(P[i]);
	}
	ll ans = inv_count(ab, a, b) - inv_count(ab0, a, b0) - inv_count(a0b, a0, b);
	std::cout << ans << " ";
	return;
}
void query() {
	std::cin >> N; Polygon H(N);
	for (int i = 0; i < N; i++) std::cin >> H[i];
	std::cin >> M; Polygon A(M);
	for (int j = 0; j < M; j++) std::cin >> A[j];
	std::cin >> Q;
	while (Q--) query(H, A);
	std::cout << "\n";
	return;
}
void solve() {
	std::cin.tie(0)->sync_with_stdio(0);
	std::cout.tie(0);
	std::cin >> Z;
	while (Z--) query();
	return;
}
int main() { solve(); return 0; }//boj18051

//#define _CRT_SECURE_NO_WARNINGS
//#include <iostream>
//#include <algorithm>
//#include <vector>
//#include <cmath>
//#include <cstring>
//#include <cassert>
//typedef long long ll;
////typedef long double ld;
//typedef double ld;
//const ld INF = 1e17;
//const ld TOL = 1e-7;
//const ld PI = acos(-1);
//const int LEN = 505;
//inline int sign(const ll& x) { return x < 0 ? -1 : !!x; }
//inline int sign(const ld& x) { return x < -TOL ? -1 : x > TOL; }
//inline bool zero(const ld& x) { return !sign(x); }
//inline ll nC2(const ll& n) { return (n - 1) * n >> 1; }
//
//int Z, N, M, Q;
//struct Pos {
//	ll x, y;
//	Pos(ll X = 0, ll Y = 0) : x(X), y(Y) {}
//	bool operator == (const Pos& p) const { return x == p.x && y == p.y; }
//	bool operator != (const Pos& p) const { return x != p.x || y != p.y; }
//	bool operator < (const Pos& p) const { return x == p.x ? y < p.y : x < p.x; }
//	bool operator <= (const Pos& p) const { return x == p.x ? y <= p.y : x <= p.x; }
//	Pos operator + (const Pos& p) const { return { x + p.x, y + p.y }; }
//	Pos operator - (const Pos& p) const { return { x - p.x, y - p.y }; }
//	Pos operator * (const int& n) const { return { x * n, y * n }; }
//	Pos operator / (const int& n) const { return { x / n, y / n }; }
//	ll operator * (const Pos& p) const { return (ll)x * p.x + (ll)y * p.y; }
//	ll operator / (const Pos& p) const { return (ll)x * p.y - (ll)y * p.x; }
//	Pos operator ^ (const Pos& p) const { return { x * p.x, y * p.y }; }
//	Pos& operator += (const Pos& p) { x += p.x; y += p.y; return *this; }
//	Pos& operator -= (const Pos& p) { x -= p.x; y -= p.y; return *this; }
//	Pos& operator *= (const int& scale) { x *= scale; y *= scale; return *this; }
//	Pos& operator /= (const int& scale) { x /= scale; y /= scale; return *this; }
//	Pos operator - () const { return { -x, -y }; }
//	Pos operator ~ () const { return { -y, x }; }
//	Pos operator ! () const { return { y, x }; }
//	ll xy() const { return (ll)x * y; }
//	ll Euc() const { return (ll)x * x + (ll)y * y; }
//	int Man() const { return std::abs(x) + std::abs(y); }
//	ld mag() const { return hypot(x, y); }
//	ld rad() const { return atan2(y, x); }
//	friend ld rad(const Pos& p1, const Pos& p2) { return atan2l(p1 / p2, p1 * p2); }
//	int quad() const { return y > 0 || y == 0 && x >= 0; }
//	friend bool cmpq(const Pos& a, const Pos& b) { return (a.quad() != b.quad()) ? a.quad() < b.quad() : a / b > 0; }
//	friend std::istream& operator >> (std::istream& is, Pos& p) { is >> p.x >> p.y; return is; }
//	friend std::ostream& operator << (std::ostream& os, const Pos& p) { os << p.x << " " << p.y; return os; }
//}; const Pos O = Pos(0, 0);
//typedef std::vector<Pos> Polygon;
//ll cross(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) / (d3 - d2); }
//int ccw(const Pos& d1, const Pos& d2, const Pos& d3) { ll ret = cross(d1, d2, d3); return sign(ret); }
//bool cmpt(const Pos& p, const Pos& q) {
//	//assert(p / q);
//	if (!(p / q)) return p.Euc() < q.Euc();
//	return p / q > 0;
//}
//Polygon graham_scan(Polygon& C) {
//	Polygon H;
//	if (C.size() < 3) {
//		std::sort(C.begin(), C.end());
//		return C;
//	}
//	std::swap(C[0], *min_element(C.begin(), C.end()));
//	std::sort(C.begin() + 1, C.end(), [&](const Pos& p, const Pos& q) -> bool {
//		int ret = ccw(C[0], p, q);
//		if (!ret) return (C[0] - p).Euc() < (C[0] - q).Euc();
//		return ret > 0;
//		}
//	);
//	C.erase(unique(C.begin(), C.end()), C.end());
//	int sz = C.size();
//	for (int i = 0; i < sz; i++) {
//		while (H.size() >= 2 && ccw(H[H.size() - 2], H.back(), C[i]) <= 0)
//			H.pop_back();
//		H.push_back(C[i]);
//	}
//	return H;
//}
//bool inner_check(const Polygon& H, const Pos& p) {
//	int sz = H.size();
//	for (int i = 0; i < sz; i++) if (cross(H[i], H[(i + 1) % sz], p) < 0) return 0;
//	return 1;
//}
//ll conquer(Polygon& C, int l, int m, int r) {
//	int i = l, j = m + 1, k = 0;
//	Polygon tmp(r - l + 1); 
//	ll cnt = 0;
//	while (i <= m && j <= r) {
//		if (cmpt(C[i], C[j])) tmp[k++] = C[i++];
//		else tmp[k++] = C[j++], cnt += ((ll)m + 1 - i);
//	}
//	while (i <= m) tmp[k++] = C[i++];
//	while (j <= r) tmp[k++] = C[j++];
//	for (i = l, k = 0; i <= r; i++, k++) C[i] = tmp[k];
//	return cnt;
//}
//ll divide(Polygon& C, int l, int r) {
//	ll cnt = 0;
//	if (l < r) {
//		int m = (l + r) >> 1;
//		cnt += divide(C, l, m);
//		cnt += divide(C, m + 1, r);
//		cnt += conquer(C, l, m, r);
//	}
//	return cnt;
//}
//ll merge_sort(Polygon& C) { return divide(C, 0, C.size() - 1); }
//ll inv_count(Polygon& C) { ll inv = merge_sort(C); return inv; }
//ll inv_count(Polygon& C, const Pos& a, const Pos& b, bool f = 0) {
//	int sz = C.size();
//	for (int i = 0; i < sz; i++) C[i] -= a;
//	std::sort(C.begin(), C.end(), cmpt);
//	for (int i = 0; i < sz; i++) C[i] += a - b;
//	ll ret = inv_count(C);
//	for (int i = 0; i < sz; i++) C[i] += b;
//	if (f) return ret;
//	ll all = nC2((ll)sz);
//	return all - ret;
//}
//void query(const Polygon& H, const Polygon& A) {
//	int a_, b_;
//	std::cin >> a_ >> b_;
//	int sz = H.size();
//	Pos a = H[a_], a0 = H[(a_ + 1) % sz], b = H[b_], b0 = H[(b_ + 1) % sz];
//	/*
//	   a --- b         a == b      a - b
//	   |     |   ||   / \      ||   \ /
//	   a0 -- b0      a0 b0           a0 == b0 
//	*/
//	Polygon S = { b0, b, a0, a }, P;
//	Polygon B = graham_scan(S);
//	sz = A.size();
//	for (int i = 0; i < sz; i++) if (inner_check(B, A[i])) P.push_back(A[i]);
//	Polygon aa0, ab, a0b0;
//	sz = P.size();
//	for (int i = 0; i < sz; i++) {
//		aa0.push_back(P[i]);
//		if (ccw(b, a, P[i]) >= 0) ab.push_back(P[i]);
//		if (ccw(a0, b0, P[i]) >= 0) a0b0.push_back(P[i]);
//	}
//	//std::cout << "FUCK:: " << inv_count(aa0, a, a0, 1) << " " <<  inv_count(ab, b, a) << " " <<  inv_count(a0b0, a0, b0) << " FUCK::\n";
//	//std::cout << "FUCK:: " << aa0.size() << " " <<  ab.size() << " " <<  a0b0.size() << " FUCK::\n";
//	ll ans = inv_count(aa0, a, a0, 1) - inv_count(ab, b, a) - inv_count(a0b0, a0, b0);
//	std::cout << ans << " ";
//	return;
//}
//void query() {
//	std::cin >> N; Polygon H(N);
//	for (int i = 0; i < N; i++) std::cin >> H[i];
//	std::cin >> M; Polygon A(M);
//	for (int j = 0; j < M; j++) std::cin >> A[j];
//	std::cin >> Q;
//	while (Q--) query(H, A);
//	std::cout << "\n";
//	return;
//}
//void solve() {
//	std::cin.tie(0)->sync_with_stdio(0);
//	std::cout.tie(0);
//	std::cin >> Z;
//	while (Z--) query();
//	return;
//}
//int main() { solve(); return 0; }//boj18051

详细

Test #1:

score: 100
Accepted
time: 419ms
memory: 3808kb

input:

116799

4
0 2
2 3
2 1
0 0
2
1 1
1 2
6
1 3
1 2
0 2
0 3
0 1
2 3

4
0 2
2 3
2 1
0 0
2
1 1
1 2
6
1 2
2 3
0 2
0 1
1 3
0 3

4
0 2
1 3
3 1
0 0
2
1 2
2 1
6
0 2
0 3
1 2
0 1
1 3
2 3

5
0 2
1 3
2 3
3 1
0 0
2
1 2
2 1
10
2 3
0 1
1 2
1 4
1 3
0 4
2 4
0 3
0 2
3 4

5
0 2
1 3
2 3
3 1
0 0
2
1 2
2 1
10
2 4
2 3
3 4
1 2
...

output:

0 0 1 0 0 0 
0 0 1 0 0 0 
1 0 0 0 0 0 
0 0 0 0 0 0 0 1 0 0 
0 0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 1 0 
0 0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 0 1 0 
0 0 0 1 0 0 0 0 0 0 
0 0 0 1 0 0 
0 0 0 1 0 0 
1 0 0 0 0 0 
0 1 0 0 0 0 
0 0 0 0 1 0 
1 0 0 0 0 0 
0 0 0 0 1 0 
0 0 0 0 1 0 
0 0 0 0 0 ...

result:

ok 116799 lines

Test #2:

score: 0
Accepted
time: 429ms
memory: 9516kb

input:

6

3
-1000000000 -1000000000
-1000000000 1000000000
1000000000 -1000000000
50000
-157866428 -481268129
-943828535 -404551206
-702156200 -918976587
-930672851 -662946583
-701356764 -690150251
-125890933 -15199649
-454987413 -601182432
-796857455 -452853385
-364662709 -332922528
-446377184 -59908020
-...

output:

422781691 405698933 421494376 
90964408 112140449 58183510 0 86959753 401170255 0 83964813 77431438 36622679 
0 0 0 201707235 298189155 0 
20661817 1108613238 83335 103419782 17196828 0 
109534039 102221733 35500923 0 107684911 381431817 0 100815183 107832883 20782102 
28845692 14952512 28864912 378...

result:

ok 6 lines

Test #3:

score: 0
Accepted
time: 684ms
memory: 3628kb

input:

150000

10
128337801 981646274
680824665 718733451
973259647 181288879
893942524 -425401883
473169741 -869603585
-128337801 -981646274
-680824665 -718733451
-973259647 -181288879
-893942524 425401883
-473169741 869603585
2
0 900000000
0 -900000000
10
4 8
1 2
6 7
5 6
0 8
6 8
1 8
3 4
5 7
0 6

10
12833...

output:

0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 ...

result:

ok 150000 lines