#include <bits/stdc++.h>
using namespace std;
#define int long long
struct pt {
int x, y;
pt(int _x = 0, int _y = 0) : x(_x), y(_y) {}
};
bool const operator == (pt a, pt b) {
return a.x == b.x && a.y == b.y;
}
pt sim(pt a, pt b) {
return pt(b.x + (b.x - a.x), b.y + (b.y - a.y));
}
int orient(pt a, pt b, pt c) {
long long val = (b.y - a.y) * 1LL * (c.x - b.x) - (b.x - a.x) * 1LL * (c.y - b.y);
return (val == 0 ? 0 : (val > 0 ? 1 : -1)); // 1 clock, -1 counterclock
}
struct angle {
pt a, b, c;
};
bool const operator == (angle p, angle q) {
return p.a == q.a && p.b == q.b && p.c == q.c;
}
bool const operator < (angle p, angle q) {
if (p == q) {
return false;
}
int ps = orient(p.a, p.b, p.c);
int qs = orient(q.a, q.b, q.c);
if (orient(p.a, q.a, p.b) == 0) {
while (true) {
}
}
if (ps == qs) {
return orient(p.a, q.a, p.b) == ps;
} else {
// ...
while (true) {
}
return false;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<pt> p(n);
vector<int> c(n);
for (int i = 0; i < n; i++) {
cin >> p[i].x >> p[i].y >> c[i];
--c[i];
}
pt a, b;
cin >> a.x >> a.y >> b.x >> b.y;
vector<vector<vector<int>>> ids(m, vector<vector<int>>(2));
vector<int> cnt(m);
for (int i = 0; i < n; i++) {
int o = orient(a, b, p[i]);
assert(o != 0);
int sd = (o == 1 ? 0 : 1);
ids[c[i]][sd].push_back(i);
cnt[c[i]] += 1;
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (orient(p[i], p[j], a) == 0) {
assert(false);
}
}
}
vector<vector<angle>> all_a(2);
vector<vector<angle>> all_b(2);
for (int i = 0; i < n; i++) {
int o = orient(a, b, p[i]);
int sd = (o == 1 ? 0 : 1);
pt p_a = sim(p[i], a);
pt p_b = sim(p[i], b);
all_a[sd].push_back({p[i], a, b});
all_b[sd].push_back({p[i], b, a});
all_a[sd ^ 1].push_back({p_a, a, b});
all_b[sd ^ 1].push_back({p_b, b, a});
}
for (int sd = 0; sd < 2; sd++) {
sort(all_a[sd].begin(), all_a[sd].end());
sort(all_b[sd].begin(), all_b[sd].end());
}
vector<int> ia(n);
vector<int> ib(n);
vector<int> ja(n);
vector<int> jb(n);
for (int i = 0; i < n; i++) {
int o = orient(a, b, p[i]);
int sd = (o == 1 ? 0 : 1);
{
angle A;
A.a = p[i];
A.b = a;
A.c = b;
int low = 0, high = (int) all_a[sd].size() - 1;
while (low <= high) {
int mid = low + high >> 1;
if (all_a[sd][mid] == A) {
ia[i] = mid;
break;
} else if (all_a[sd][mid] < A) {
low = mid + 1;
} else {
high = mid - 1;
}
}
//ia[i] = (int) (lower_bound(all_a[sd].begin(), all_a[sd].end(), A) - all_a[sd].begin());
assert(A == all_a[sd][ia[i]]);
}
{
angle A;
A.a = p[i];
A.b = b;
A.c = a;
int low = 0, high = (int) all_b[sd].size() - 1;
while (low <= high) {
int mid = low + high >> 1;
if (all_b[sd][mid] == A) {
ib[i] = mid;
break;
} else if (all_b[sd][mid] < A) {
low = mid + 1;
} else {
high = mid - 1;
}
}
//ib[i] = (int) (lower_bound(all_b[sd].begin(), all_b[sd].end(), A) - all_b[sd].begin());
assert(A == all_b[sd][ib[i]]);
}
{
angle A;
A.a = sim(p[i], a);
A.b = a;
A.c = b;
int low = 0, high = all_a[sd ^ 1].size() - 1;
while (low <= high) {
int mid = low + high >> 1;
if (all_a[sd ^ 1][mid] == A) {
ja[i] = mid;
break;
} else if (all_a[sd ^ 1][mid] < A) {
low = mid + 1;
} else {
high = mid - 1;
}
}
//ja[i] = (int) (lower_bound(all_a[sd ^ 1].begin(), all_a[sd ^ 1].end(), A) - all_a[sd ^ 1].begin());
assert(A == all_a[sd ^ 1][ja[i]]);
}
{
angle A;
A.a = sim(p[i], b);
A.b = b;
A.c = a;
int low = 0, high = all_b[sd ^ 1].size() - 1;
while (low <= high) {
int mid = low + high >> 1;
if (all_b[sd ^ 1][mid] == A) {
jb[i] = mid;
break;
} else if (all_b[sd ^ 1][mid] < A) {
low = mid + 1;
} else {
high = mid - 1;
}
}
//jb[i] = (int) (lower_bound(all_b[sd ^ 1].begin(), all_b[sd ^ 1].end(), A) - all_b[sd ^ 1].begin());
assert(A == all_b[sd ^ 1][jb[i]]);
}
}
int q;
cin >> q;
vector<int> f(q), g(q);
for (int i = 0; i < q; i++) {
cin >> f[i] >> g[i];
--f[i]; --g[i];
}
vector<int> qt(q, -1);
map<pair<int, int>, int> mp;
for (int i = 0; i < q; i++) {
if (mp.count({f[i], g[i]})) {
//qt[i] = mp[{f[i], g[i]}];
} else {
//mp[{f[i], g[i]}] = i;
}
}
vector<int> res(q);
{
vector<vector<vector<vector<pair<int, int>>>>> qs(m, vector<vector<vector<pair<int, int>>>>(2));
for (int i = 0; i < m; i++) {
qs[i][0].resize(cnt[i]);
qs[i][1].resize(cnt[i]);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < 2; j++) {
sort(ids[i][j].begin(), ids[i][j].end(), [&](int i, int j) {
return ia[i] < ia[j];
});
}
}
for (int qq = 0; qq < q; qq++) {
if (qt[qq] != -1) {
continue;
}
if (min(cnt[f[qq]], cnt[g[qq]]) == 0) {
continue;
}
if (cnt[f[qq]] <= cnt[g[qq]]) {
for (int sd = 0; sd < 2; sd++) {
for (int i : ids[f[qq]][sd]) {
{
int low = 0, high = (int) ids[g[qq]][sd].size() - 1, pos = -1;
while (low <= high) {
int mid = low + high >> 1;
if (ia[i] >= ia[ids[g[qq]][sd][mid]]) {
pos = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
if (pos != -1) {
qs[g[qq]][sd][pos].emplace_back(qq, ib[i]);
}
}
{
int low = 0, high = (int) ids[g[qq]][sd ^ 1].size() - 1, pos = -1;
while (low <= high) {
int mid = low + high >> 1;
if (ja[i] >= ia[ids[g[qq]][sd ^ 1][mid]]) {
pos = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
if (pos != -1) {
qs[g[qq]][sd ^ 1][pos].emplace_back(qq, jb[i]);
}
}
}
}
}
}
vector<int> fenw(n);
auto Modify = [&](int x, int v) {
while (x < n) {
fenw[x] += v;
x |= (x + 1);
}
};
auto Query = [&](int x) {
int v = 0;
while (x >= 0) {
v += fenw[x];
x = (x & (x + 1)) - 1;
}
return v;
};
for (int i = 0; i < m; i++) {
for (int j = 0; j < 2; j++) {
int sz = (int) ids[i][j].size();
for (int k = 0; k < sz; k++) {
Modify(ib[ids[i][j][k]], +1);
for (auto& p : qs[i][j][k]) {
res[p.first] += Query(p.second);
}
}
for (int k = 0; k < sz; k++) {
Modify(ib[ids[i][j][k]], -1);
}
}
}
}
{
/* vector<vector<vector<vector<pair<int, int>>>>> qs(m, vector<vector<vector<pair<int, int>>>>(2));
for (int i = 0; i < m; i++) {
qs[i][0].resize(cnt[i]);
qs[i][1].resize(cnt[i]);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < 2; j++) {
sort(ids[i][j].begin(), ids[i][j].end(), [&](int i, int j) {
return ia[i] > ia[j];
});
}
}
for (int qq = 0; qq < q; qq++) {
if (qt[qq] != -1) {
continue;
}
if (min(cnt[f[qq]], cnt[g[qq]]) == 0) {
continue;
}
if (cnt[f[qq]] > cnt[g[qq]]) {
for (int sd = 0; sd < 2; sd++) {
for (int i : ids[g[qq]][sd]) {
{
int low = 0, high = (int) ids[f[qq]][sd].size() - 1, pos = -1;
while (low <= high) {
int mid = low + high >> 1;
if (ia[ids[f[qq]][sd][mid]] >= ia[i]) {
pos = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
if (pos != -1) {
qs[f[qq]][sd][pos].emplace_back(qq, ib[i]);
}
}
}
}
}
vector<int> fenw(n);
auto Modify = [&](int x, int v) {
assert(0 <= x);
while (x < n) {
fenw[x] += v;
x |= (x + 1);
}
};
auto Query = [&](int x) {
assert(x < n);
int v = 0;
while (x >= 0) {
v += fenw[x];
x = (x & (x + 1)) - 1;
}
return v;
};
for (int i = 0; i < m; i++) {
for (int j = 0; j < 2; j++) {
int sz = (int) ids[i][j].size();
for (int k = 0; k < sz; k++) {
Modify(ib[ids[i][j][k]], +1);
for (auto& p : qs[i][j][k]) {
res[p.first] += Query(n - 1) - Query(p.second - 1);
}
}
for (int k = 0; k < sz; k++) {
Modify(ib[ids[i][j][k]], -1);
}
}
}
} */
for (int qq = 0; qq < q; qq++) {
if (cnt[f[qq]] > cnt[g[qq]]) {
for (int sd = 0; sd < 2; sd++) {
for (int i : ids[f[qq]][sd]) {
for (int j : ids[g[qq]][sd]) {
if (ia[i] >= ia[j] && ib[i] >= ib[j]) {
res[qq] += 1;
}
}
}
}
}
}
}
{
/* vector<vector<vector<vector<pair<int, int>>>>> qs(m, vector<vector<vector<pair<int, int>>>>(2));
for (int i = 0; i < m; i++) {
qs[i][0].resize(cnt[i]);
qs[i][1].resize(cnt[i]);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < 2; j++) {
sort(ids[i][j].begin(), ids[i][j].end(), [&](int x, int y) {
return ja[x] > ja[y];
});
}
}
for (int qq = 0; qq < q; qq++) {
if (qt[qq] != -1) {
continue;
}
if (min(cnt[f[qq]], cnt[g[qq]]) == 0) {
continue;
}
if (cnt[f[qq]] > cnt[g[qq]]) {
for (int sd = 0; sd < 2; sd++) {
for (int i : ids[g[qq]][sd]) {
int pos = -1;
while (pos + 1 < (int) ids[f[qq]][sd ^ 1].size() && ja[ids[f[qq]][sd ^ 1][pos + 1]] >= ia[i]) {
pos += 1;
}
if (pos != -1) {
qs[f[qq]][sd ^ 1][pos].emplace_back(qq, ib[i]);
}
{
int low = 0, high = (int) ids[f[qq]][sd ^ 1].size() - 1, pos = -1;
while (low <= high) {
int mid = low + high >> 1;
if (ja[ids[f[qq]][sd ^ 1][mid]] >= ia[i]) {
pos = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
if (pos != -1) {
qs[f[qq]][sd ^ 1][pos].emplace_back(qq, ib[i]);
}
}
}
}
}
vector<int> fenw(n);
auto Modify = [&](int x, int v) {
assert(0 <= x);
while (x < n) {
fenw[x] += v;
x |= (x + 1);
}
};
auto Query = [&](int x) {
assert(x < n);
int v = 0;
while (x >= 0) {
v += fenw[x];
x = (x & (x + 1)) - 1;
}
return v;
};
for (int i = 0; i < m; i++) {
for (int j = 0; j < 2; j++) {
int sz = (int) ids[i][j].size();
for (int k = 0; k < sz; k++) {
// Modify(jb[ids[i][j][k]], +1);
for (auto& p : qs[i][j][k]) {
for (int w = 0; w <= k; w++) {
if (jb[ids[i][j][w]] >= p.second) {
res[p.first] += 1;
}
}
// res[p.first] += Query(n - 1) - Query(p.second - 1);
}
}
for (int k = 0; k < sz; k++) {
// Modify(jb[ids[i][j][k]], -1);
}
}
}
} */
for (int qq = 0; qq < q; qq++) {
if (cnt[f[qq]] > cnt[g[qq]]) {
for (int sd = 0; sd < 2; sd++) {
for (int i : ids[g[qq]][sd]) {
for (int j : ids[f[qq]][sd ^ 1]) {
if (ja[j] < ia[i]) {
break;
}
if (jb[j] >= ib[i]) {
res[qq] += 1;
}
}
}
}
}
}
}
for (int i = 0; i < q; i++) {
if (qt[i] != -1) {
res[i] = res[qt[i]];
}
}
for (int i = 0; i < q; i++) {
cout << res[i] << '\n';
}
return 0;
}
Compilation message
dragon2.cpp: In function 'int main()':
dragon2.cpp:114:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
114 | int mid = low + high >> 1;
| ~~~~^~~~~~
dragon2.cpp:134:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
134 | int mid = low + high >> 1;
| ~~~~^~~~~~
dragon2.cpp:154:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
154 | int mid = low + high >> 1;
| ~~~~^~~~~~
dragon2.cpp:174:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
174 | int mid = low + high >> 1;
| ~~~~^~~~~~
dragon2.cpp:231:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
231 | int mid = low + high >> 1;
| ~~~~^~~~~~
dragon2.cpp:246:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
246 | int mid = low + high >> 1;
| ~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
1220 KB |
Output is correct |
| 2 |
Correct |
20 ms |
1564 KB |
Output is correct |
| 3 |
Correct |
29 ms |
4664 KB |
Output is correct |
| 4 |
Correct |
47 ms |
7704 KB |
Output is correct |
| 5 |
Correct |
59 ms |
5984 KB |
Output is correct |
| 6 |
Correct |
15 ms |
2072 KB |
Output is correct |
| 7 |
Correct |
15 ms |
2072 KB |
Output is correct |
| 8 |
Correct |
22 ms |
1372 KB |
Output is correct |
| 9 |
Correct |
24 ms |
1460 KB |
Output is correct |
| 10 |
Correct |
24 ms |
1500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1189 ms |
9508 KB |
Output is correct |
| 2 |
Correct |
1168 ms |
12920 KB |
Output is correct |
| 3 |
Correct |
669 ms |
10224 KB |
Output is correct |
| 4 |
Correct |
658 ms |
9808 KB |
Output is correct |
| 5 |
Correct |
675 ms |
15748 KB |
Output is correct |
| 6 |
Correct |
665 ms |
9972 KB |
Output is correct |
| 7 |
Correct |
657 ms |
9972 KB |
Output is correct |
| 8 |
Correct |
669 ms |
9944 KB |
Output is correct |
| 9 |
Correct |
662 ms |
10312 KB |
Output is correct |
| 10 |
Correct |
658 ms |
9952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
1220 KB |
Output is correct |
| 2 |
Correct |
20 ms |
1564 KB |
Output is correct |
| 3 |
Correct |
29 ms |
4664 KB |
Output is correct |
| 4 |
Correct |
47 ms |
7704 KB |
Output is correct |
| 5 |
Correct |
59 ms |
5984 KB |
Output is correct |
| 6 |
Correct |
15 ms |
2072 KB |
Output is correct |
| 7 |
Correct |
15 ms |
2072 KB |
Output is correct |
| 8 |
Correct |
22 ms |
1372 KB |
Output is correct |
| 9 |
Correct |
24 ms |
1460 KB |
Output is correct |
| 10 |
Correct |
24 ms |
1500 KB |
Output is correct |
| 11 |
Correct |
1189 ms |
9508 KB |
Output is correct |
| 12 |
Correct |
1168 ms |
12920 KB |
Output is correct |
| 13 |
Correct |
669 ms |
10224 KB |
Output is correct |
| 14 |
Correct |
658 ms |
9808 KB |
Output is correct |
| 15 |
Correct |
675 ms |
15748 KB |
Output is correct |
| 16 |
Correct |
665 ms |
9972 KB |
Output is correct |
| 17 |
Correct |
657 ms |
9972 KB |
Output is correct |
| 18 |
Correct |
669 ms |
9944 KB |
Output is correct |
| 19 |
Correct |
662 ms |
10312 KB |
Output is correct |
| 20 |
Correct |
658 ms |
9952 KB |
Output is correct |
| 21 |
Correct |
1226 ms |
9640 KB |
Output is correct |
| 22 |
Correct |
1069 ms |
13088 KB |
Output is correct |
| 23 |
Correct |
1142 ms |
44732 KB |
Output is correct |
| 24 |
Correct |
1020 ms |
77380 KB |
Output is correct |
| 25 |
Correct |
704 ms |
19808 KB |
Output is correct |
| 26 |
Correct |
697 ms |
20388 KB |
Output is correct |
| 27 |
Correct |
665 ms |
16912 KB |
Output is correct |
| 28 |
Correct |
678 ms |
16912 KB |
Output is correct |
| 29 |
Correct |
1827 ms |
19668 KB |
Output is correct |
| 30 |
Correct |
695 ms |
19044 KB |
Output is correct |
| 31 |
Correct |
686 ms |
19128 KB |
Output is correct |
| 32 |
Correct |
702 ms |
20020 KB |
Output is correct |
| 33 |
Correct |
926 ms |
49320 KB |
Output is correct |
| 34 |
Correct |
691 ms |
19148 KB |
Output is correct |
| 35 |
Correct |
690 ms |
19504 KB |
Output is correct |
| 36 |
Correct |
695 ms |
20272 KB |
Output is correct |
| 37 |
Correct |
707 ms |
20264 KB |
Output is correct |
| 38 |
Correct |
993 ms |
48592 KB |
Output is correct |
| 39 |
Correct |
998 ms |
52368 KB |
Output is correct |
| 40 |
Correct |
947 ms |
51544 KB |
Output is correct |
| 41 |
Correct |
1400 ms |
20084 KB |
Output is correct |
| 42 |
Correct |
1070 ms |
21168 KB |
Output is correct |
| 43 |
Correct |
1040 ms |
22568 KB |
Output is correct |
| 44 |
Correct |
1519 ms |
13248 KB |
Output is correct |
| 45 |
Correct |
1101 ms |
13244 KB |
Output is correct |
| 46 |
Correct |
942 ms |
13092 KB |
Output is correct |
| 47 |
Correct |
673 ms |
13932 KB |
Output is correct |
| 48 |
Correct |
677 ms |
14232 KB |
Output is correct |
| 49 |
Correct |
664 ms |
13804 KB |
Output is correct |
