QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#547226 | #3034. Antennas | crimson231 | AC ✓ | 493ms | 5800kb | C++17 | 8.5kb | 2024-09-04 19:22:56 | 2024-09-04 19:22:56 |
Judging History
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 = 50005;
inline int sign(const ll& x) { return x < 0 ? -1 : !!x; }
inline ll nC2(const ll& n) { return (n - 1) * n >> 1; }
int Z, N, M, Q;
struct Pos {
int x, y;
Pos(int X = 0, int 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; }
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 }; }
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) { 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 }; }
ll Euc() const { return (ll)x * x + (ll)y * y; }
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) { return sign(cross(d1, d2, d3)); }
bool cmpt(const Pos& p, const Pos& q) { assert(p / q); return p / q ? p / q > 0 : p.Euc() < q.Euc(); }
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) {
if (l >= r) return 0;
ll cnt = 0;
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, 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 - merge_sort(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 ab, a0b, ab0;
sz = A.size();
for (int i = 0; i < sz; i++) {
if (cross(a0, b0, A[i]) >= 0 && cross(b, a, A[i]) >= 0) ab.push_back(A[i]);
if (cross(a0, b0, A[i]) >= 0 && cross(b0, a, A[i]) >= 0) ab0.push_back(A[i]);
if (cross(a0, b0, A[i]) >= 0 && cross(b, a0, A[i]) >= 0) a0b.push_back(A[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 = 50005;
//inline int sign(const ll& x) { return x < 0 ? -1 : !!x; }
//inline ll nC2(const ll& n) { return (n - 1) * n >> 1; }
//
//int Z, N, M, Q;
//struct Pos {
// int x, y;
// Pos(int X = 0, int 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; }
// 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 }; }
// 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) { 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 }; }
// ll Euc() const { return (ll)x * x + (ll)y * y; }
// 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) { return sign(cross(d1, d2, d3)); }
//bool cmpt(const Pos& p, const Pos& q) { assert(p / q); return p / q ? p / q > 0 : p.Euc() < q.Euc(); }
//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) {
// if (l >= r) return 0;
// ll cnt = 0;
// 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, 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 - merge_sort(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 ab, a0b, ab0;
// sz = A.size();
// for (int i = 0; i < sz; i++) {
// if (ccw(a0, b0, A[i]) >= 0 && ccw(b, a, A[i]) >= 0) ab.push_back(A[i]);
// if (ccw(a0, b0, A[i]) >= 0 && ccw(b0, a, A[i]) >= 0) ab0.push_back(A[i]);
// if (ccw(a0, b0, A[i]) >= 0 && ccw(b, a0, A[i]) >= 0) a0b.push_back(A[i]);
// }
// ll ans = inv_count(ab, a, b) - inv_count(ab0, a, b0) - inv_count(a0b, a0, b);
// //std::cout << "FUCK:: " << inv_count(ab, a, b) << " fuck:: " << inv_count(ab0, a, b0) << " fuck:: " << inv_count(a0b, a0, b) << "\n";
// //std::cout << "SUCK:: " << ab.size() << " suck:: " << ab0.size() << " suck:: " << a0b.size() << "\n";
// 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
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 274ms
memory: 3576kb
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: 424ms
memory: 5800kb
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: 493ms
memory: 3636kb
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